JPH0679342B2 - 画像生成装置 - Google Patents
画像生成装置Info
- Publication number
- JPH0679342B2 JPH0679342B2 JP60291621A JP29162185A JPH0679342B2 JP H0679342 B2 JPH0679342 B2 JP H0679342B2 JP 60291621 A JP60291621 A JP 60291621A JP 29162185 A JP29162185 A JP 29162185A JP H0679342 B2 JPH0679342 B2 JP H0679342B2
- Authority
- JP
- Japan
- Prior art keywords
- image
- image generation
- calculation time
- computer
- node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000004364 calculation method Methods 0.000 claims description 28
- 238000000034 method Methods 0.000 description 11
- 238000010586 diagram Methods 0.000 description 5
- 230000000694 effects Effects 0.000 description 5
- 238000012545 processing Methods 0.000 description 3
- 238000011960 computer-aided design Methods 0.000 description 2
- 230000004044 response Effects 0.000 description 2
- 238000007796 conventional method Methods 0.000 description 1
- 238000005286 illumination Methods 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
- 238000004519 manufacturing process Methods 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 238000005070 sampling Methods 0.000 description 1
Landscapes
- Multi Processors (AREA)
- Image Processing (AREA)
- Image Generation (AREA)
Description
【発明の詳細な説明】 産業上の利用分野 本発明は、CAD（Computer Aided Design）,CAM（Comp
uter Aided Manufacturing）等に用いられる高速画像
生成装置に関する。
uter Aided Manufacturing）等に用いられる高速画像
生成装置に関する。
従来の技術 計算機を用いて数値から三次元形状を生成するアルゴリ
ズムには、スキャンライン法（Scanlinemethod）,Zバッ
ファ法（ZBuffer method），レイトレーシング法（Ray
tacing algorithm）があるが、中でも、文献T.Whitt
ed「An Illumination Model for Shaded Displa
y」“Communications of the ACM（コミュニケーシ
ョンズ オブ ジ エーシ−エム）,June,1980,Vol.23,
No.6"に詳しいレイトレーシングアルゴリズムは、簡単
でリアルな画像を生成できる。第２図を用いてその概要
を説明する。
ズムには、スキャンライン法（Scanlinemethod）,Zバッ
ファ法（ZBuffer method），レイトレーシング法（Ray
tacing algorithm）があるが、中でも、文献T.Whitt
ed「An Illumination Model for Shaded Displa
y」“Communications of the ACM（コミュニケーシ
ョンズ オブ ジ エーシ−エム）,June,1980,Vol.23,
No.6"に詳しいレイトレーシングアルゴリズムは、簡単
でリアルな画像を生成できる。第２図を用いてその概要
を説明する。
第２図において、１は視線、２は画面内の要素（i,
j）、３は物体の投影される画面、4,5は３次元空間上の
物体、６は視点、７は交点、８は光源である。視点６か
ら発せられ、画面３上の画素（i,j）２を通過する視線
１と物体4,5との交点を求め、より前記視点６に近い物
体、この場合は前記物体４であるが、前記視線１と前記
物体４との交点７について、次に示すphongのモデルに
したがって、輝度を計算し、前記画素（i,j）２の輝度
とする。以上の操作を全画素について行うことにより、
画像を得る。
j）、３は物体の投影される画面、4,5は３次元空間上の
物体、６は視点、７は交点、８は光源である。視点６か
ら発せられ、画面３上の画素（i,j）２を通過する視線
１と物体4,5との交点を求め、より前記視点６に近い物
体、この場合は前記物体４であるが、前記視線１と前記
物体４との交点７について、次に示すphongのモデルに
したがって、輝度を計算し、前記画素（i,j）２の輝度
とする。以上の操作を全画素について行うことにより、
画像を得る。
phongのモデル しかし、欠点としては、３次元空間上の物体との交差判
定に時間を要することや各画素についての計算を全画素
について行うことに起因する膨大な計算値にある。
定に時間を要することや各画素についての計算を全画素
について行うことに起因する膨大な計算値にある。
この欠点を補う一手法として、文献西村他「LINKS−1:
コンピュータグラフィックシステム」（情報処理学会マ
イクロコンピュータ研究会資料,24−１（1982,11,2））
では、レイトレーシングアルゴリズムに内在する並列処
理の可能性、すなわち、各画素の計算は、他の画素とは
全く独立に実行可能な点に注目し、大規模な並列処理を
採用することにより、前記の膨大な計算を短くしてい
る。第３図を用いて、前記LINKS-1の基本構成を示す。
第３図において、９はデータベース、10はノードコンピ
ュータを制御監視するコントロールプロセッサであるル
ートコンピュータ、11は、画面の小領域内の画素の輝度
を前記レイトレーシングアルゴリズムを用いて計算する
プロセッサエレメントであるノードコンピュータ、12は
ノードコンピュータにおいて計算された画素の輝度をフ
レームメモリに集めるデータコレクタ、13は前記データ
コレクタによって集められた輝度を貯えるフレームメモ
リ、14はフレームメモリの内容を表示するCRTディスプ
レイである。
コンピュータグラフィックシステム」（情報処理学会マ
イクロコンピュータ研究会資料,24−１（1982,11,2））
では、レイトレーシングアルゴリズムに内在する並列処
理の可能性、すなわち、各画素の計算は、他の画素とは
全く独立に実行可能な点に注目し、大規模な並列処理を
採用することにより、前記の膨大な計算を短くしてい
る。第３図を用いて、前記LINKS-1の基本構成を示す。
第３図において、９はデータベース、10はノードコンピ
ュータを制御監視するコントロールプロセッサであるル
ートコンピュータ、11は、画面の小領域内の画素の輝度
を前記レイトレーシングアルゴリズムを用いて計算する
プロセッサエレメントであるノードコンピュータ、12は
ノードコンピュータにおいて計算された画素の輝度をフ
レームメモリに集めるデータコレクタ、13は前記データ
コレクタによって集められた輝度を貯えるフレームメモ
リ、14はフレームメモリの内容を表示するCRTディスプ
レイである。
データベース９に入力されている、三次元空間上の物体
を示す数値は、ルートコンピュータ10を介して、ノード
コンピュータ11に送られる。次に、ルートコンピュータ
10は、画面を小領域に分割し、前記ノードコンピュータ
11に割りあてる。前記ノードコンピュータは、割りあて
られた小領域内の画素について、レイトレーシングアル
ゴリズムにもとづき画像生成を行なう。割りあてられた
小領域内の画素の画像生成が終了したノードコンピュー
タは、前記ルートコンピュータに未生成の小領域を要求
し、なければ、画像生成を終了する。前記ノードコンピ
ュータで求められた輝度は、データコレクタ12を介し
て、フレームメモリ13に貯えられ、CRT14に表示され
る。すべてのノードコンピュータが各々割りあてられた
小領域の画像生成を終了し、未生成の小領域がなくなっ
た時点で、一画面の画像生成を終了する。
を示す数値は、ルートコンピュータ10を介して、ノード
コンピュータ11に送られる。次に、ルートコンピュータ
10は、画面を小領域に分割し、前記ノードコンピュータ
11に割りあてる。前記ノードコンピュータは、割りあて
られた小領域内の画素について、レイトレーシングアル
ゴリズムにもとづき画像生成を行なう。割りあてられた
小領域内の画素の画像生成が終了したノードコンピュー
タは、前記ルートコンピュータに未生成の小領域を要求
し、なければ、画像生成を終了する。前記ノードコンピ
ュータで求められた輝度は、データコレクタ12を介し
て、フレームメモリ13に貯えられ、CRT14に表示され
る。すべてのノードコンピュータが各々割りあてられた
小領域の画像生成を終了し、未生成の小領域がなくなっ
た時点で、一画面の画像生成を終了する。
発明が解決しようとする問題点 前記画像生成システムでは、すべてのノードコンピュー
タの計算が同時に終了しないため、ノードコンピュータ
の台数に比例した効果をあげていない。また、ルートコ
ンピュータへのノードコンピュータからの要求が一時期
を集中し、ノードコンピュータの中には割りあて待ちの
時間が長くなるものも生じ、この点で、台数に比例した
効果を得にくい。
タの計算が同時に終了しないため、ノードコンピュータ
の台数に比例した効果をあげていない。また、ルートコ
ンピュータへのノードコンピュータからの要求が一時期
を集中し、ノードコンピュータの中には割りあて待ちの
時間が長くなるものも生じ、この点で、台数に比例した
効果を得にくい。
問題点を解決するための手段 画面をある粗さでサンプリングしてえらんだ画素を選ぶ
手段とその画素計算時間を求める手段とその計算時間値
を前記画素を含む小領域の平均計算時間とし、この値を
もとに、各ノードコンピュータの計算時間が均等になる
ように画面分割した小領域を各ノードコンピュータの割
りあてる手段とから成る画像生成方式。
手段とその画素計算時間を求める手段とその計算時間値
を前記画素を含む小領域の平均計算時間とし、この値を
もとに、各ノードコンピュータの計算時間が均等になる
ように画面分割した小領域を各ノードコンピュータの割
りあてる手段とから成る画像生成方式。
作用 本発明は前記した方式により、ノードコンピュータの計
算時間が均等になると、各ノードコンピュータの計算の
終了が同一となって、ノードコンピュータの台数に比例
した効果をあげる。
算時間が均等になると、各ノードコンピュータの計算の
終了が同一となって、ノードコンピュータの台数に比例
した効果をあげる。
実施例 第１図は本発明のフローチャートである。以下、第１図
をもとに本発明を説明する。
をもとに本発明を説明する。
第１図において、第３図のルートコンピュータ10から起
動がかかり、第３図のノードコンピュータ11が稼動を始
める。
動がかかり、第３図のノードコンピュータ11が稼動を始
める。
レイトレーシングアルゴリズムを用いて画像生成を行う
場合、隣接する画素では、各視線が同一の物体と交差す
る確率が高い。したがって、ある画素の計算時間で前記
画素を含む小領域の画素についての平均計算時間を代表
させることができる。したがって、第１図に示すよう
に、ルートコンピュータ10は各ノードコンピュータ11に
粗めの画素の割りあてを行なう。このときの粗めの画素
（i,j）21と前記画素（i,j）を含む小領域（i,j）22か
ら構成される画面を第４図に示す。破線は、小領域（i,
j）の境界を示す。
場合、隣接する画素では、各視線が同一の物体と交差す
る確率が高い。したがって、ある画素の計算時間で前記
画素を含む小領域の画素についての平均計算時間を代表
させることができる。したがって、第１図に示すよう
に、ルートコンピュータ10は各ノードコンピュータ11に
粗めの画素の割りあてを行なう。このときの粗めの画素
（i,j）21と前記画素（i,j）を含む小領域（i,j）22か
ら構成される画面を第４図に示す。破線は、小領域（i,
j）の境界を示す。
画素（i,j）21の割りあてを受けたリードコンピュータ1
1は、第１図に示すところの画素の画像生成を行なう。
1は、第１図に示すところの画素の画像生成を行なう。
ノードコンピュータ11は、ルートコンピュータに第１図
に示すところの各画素の計算時間の返答を行なう。この
ときの各画素（i,j）21の計算時間を縦軸に、各画素
（i,j）21を横軸にとったグラフが第６図である。
に示すところの各画素の計算時間の返答を行なう。この
ときの各画素（i,j）21の計算時間を縦軸に、各画素
（i,j）21を横軸にとったグラフが第６図である。
次に、ルートコンピュータ10において、先に求めた画素
（i,j）21の計算時間をもとに各ノードコンピュータ11
の計算時間が均等になるように画面分割した小領域（i,
j）22を各ノードコンピュータに割りあてる。このとき
の均等化する問題は、文献「Operating System Theor
y（オペレーティング システム セオリー）」（Edwar
d G.Coffman Jr.,Peter J.Denning）によればNP−co
mplete（Non−Polynominal complete）すなわち、多項
式時間では解けない問題でヒューリスティックな手法が
必要である。この代表的な手法が、LPT（Largest Proc
essing Time）問題といわれる。LPT問題は、計算時間
の長いものから順にノードコンピュータ11への割りあて
を決めていくと、各ノードコンピュータ11の計算時間を
最大最適解の に抑えることができることを示している。ｍはノードコ
ンピュータの台数を示す。
（i,j）21の計算時間をもとに各ノードコンピュータ11
の計算時間が均等になるように画面分割した小領域（i,
j）22を各ノードコンピュータに割りあてる。このとき
の均等化する問題は、文献「Operating System Theor
y（オペレーティング システム セオリー）」（Edwar
d G.Coffman Jr.,Peter J.Denning）によればNP−co
mplete（Non−Polynominal complete）すなわち、多項
式時間では解けない問題でヒューリスティックな手法が
必要である。この代表的な手法が、LPT（Largest Proc
essing Time）問題といわれる。LPT問題は、計算時間
の長いものから順にノードコンピュータ11への割りあて
を決めていくと、各ノードコンピュータ11の計算時間を
最大最適解の に抑えることができることを示している。ｍはノードコ
ンピュータの台数を示す。
次に、第１図に示す小領域の割りあてを行う。先に求め
た均等化された割りあてにもとづいて、ルートコンピュ
ータ10からノードコンピュータ11への割りあてを行な
う。
た均等化された割りあてにもとづいて、ルートコンピュ
ータ10からノードコンピュータ11への割りあてを行な
う。
次に、ノードコンピュータ11は、割りあてられた小画面
の画像生成をレイトレーシングアルゴリズムにもとづい
て実行する。
の画像生成をレイトレーシングアルゴリズムにもとづい
て実行する。
各ノードコンピュータ11は、割りあてられた複数の小領
域（i,j）22の画像生成が終了したことをルートコッピ
ュータ10に伝える。
域（i,j）22の画像生成が終了したことをルートコッピ
ュータ10に伝える。
ルートコンピュータ10は、すべてのノードコンピュータ
11が割りあてられた複数の小領域（i,j）22の画像生成
が終了したら、一画面の画像生成を終了する。
11が割りあてられた複数の小領域（i,j）22の画像生成
が終了したら、一画面の画像生成を終了する。
従来の技術では、ノードコンピュータ11に小領域（i,
j）22を１つずつ割りあて、前記小領域（i,j）22の画像
生成が終了した時点で次の小領域（i,j）22を割りあて
ているため、仮にルートコンピュータ10に接がるノード
コンピュータ11の数を増やしていけば、ノードコンピュ
ータ11の台数だけの並列処理が可能になるが、あるとこ
ろでルートコンピュータ10へのアクセスの競合が生じ、
ノードコンピュータ11に対する応答が悪くなるため、ノ
ードコンピュータの台数を増やしつづけても台数だけの
並列処理にはならなくなる。
j）22を１つずつ割りあて、前記小領域（i,j）22の画像
生成が終了した時点で次の小領域（i,j）22を割りあて
ているため、仮にルートコンピュータ10に接がるノード
コンピュータ11の数を増やしていけば、ノードコンピュ
ータ11の台数だけの並列処理が可能になるが、あるとこ
ろでルートコンピュータ10へのアクセスの競合が生じ、
ノードコンピュータ11に対する応答が悪くなるため、ノ
ードコンピュータの台数を増やしつづけても台数だけの
並列処理にはならなくなる。
しかし、本方式を用いれば、ノードコンピュータ11に対
するルートコンピュータ10の応答の問題は一度に全画面
の領域が割りあてられるため、画像生成実行中には回避
される。その結果、ノードコンピュータ11の台数の比例
した効果が得られる。
するルートコンピュータ10の応答の問題は一度に全画面
の領域が割りあてられるため、画像生成実行中には回避
される。その結果、ノードコンピュータ11の台数の比例
した効果が得られる。
発明の効果 上述の説明から明らかなように本発明によれば、ルート
コンピュータへのノードコンピュータのアクセス競合は
おこらない。又、それによって、ノードコンピュータの
割りあて待ちが生じることがなく、高速の画像生成を可
能にできる。
コンピュータへのノードコンピュータのアクセス競合は
おこらない。又、それによって、ノードコンピュータの
割りあて待ちが生じることがなく、高速の画像生成を可
能にできる。
更に割りあて待ちが生じることがないので、画像生成を
実行するノードコンピュータの台数を大幅に増加し台数
に比例して高速に画像を生成することができる。
実行するノードコンピュータの台数を大幅に増加し台数
に比例して高速に画像を生成することができる。
第１図は、ルートコンピュータとノードコンピュータの
第Ｏ番から第ｎ番までの処理のフローチャート、第２図
は、レイトレーシングアルゴリズムを示す図、第３図
は、従来の画像生成システム図、第４図は生成画像の簡
略図、第５図は、分割画面を示す図、第６図は、画素
（i,j）の計算時間の分布を示す図、第７図は、各ノー
ドコンピュータの計算時間の分布を示す図である。 ９……データベース、10……ルートコンピュータ、11…
…ノードコンピュータ、12……データコレクタ、13……
フレームメモリ、14……CRTディスプレイ。
第Ｏ番から第ｎ番までの処理のフローチャート、第２図
は、レイトレーシングアルゴリズムを示す図、第３図
は、従来の画像生成システム図、第４図は生成画像の簡
略図、第５図は、分割画面を示す図、第６図は、画素
（i,j）の計算時間の分布を示す図、第７図は、各ノー
ドコンピュータの計算時間の分布を示す図である。 ９……データベース、10……ルートコンピュータ、11…
…ノードコンピュータ、12……データコレクタ、13……
フレームメモリ、14……CRTディスプレイ。
Claims (4)
- 【請求項１】画面の画像生成の際に、画面を複数の小領
域に分割する領域分割手段と、前記各小領域内の画素の
画像生成を実行する複数のプロセッサエレメントと、前
記プロセッサエレメントにバスまたは共有メモリを介し
て接続され、前記プロセッサエレメントを制御監視する
コントロールプロセッサとを備えた画像生成に用いる装
置であって、 前記各小領域の画像生成に要する計算時間を概算する概
算手段と、 前記概算手段で求めた計算時間に基づいて、前記各プロ
セッサエレメントの計算時間が均等になるように、前記
各プロセッサエレメントに複数の小領域の計算を割り当
てる領域割当手段とを備えた画像生成装置。 - 【請求項２】領域割当手段が、概算手段で求めた計算時
間の長い小領域から順に、プロセッサエレメントに割り
当てることを特徴とする特許請求の範囲第１項記載の画
像生成装置。 - 【請求項３】プロセッサエレメントが、レイトレーシン
グアルゴリズムを用いて、画素の画像生成を行うことを
特徴とする特許請求の範囲第１項または第２項記載の画
像生成装置。 - 【請求項４】概算手段が、ある画素の画像生成に要した
計算時間を、その画素を含む小領域の概算計算時間とす
ることを特徴とする特許請求の範囲第１項〜第３項何れ
かに記載の画像生成装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60291621A JPH0679342B2 (ja) | 1985-12-24 | 1985-12-24 | 画像生成装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60291621A JPH0679342B2 (ja) | 1985-12-24 | 1985-12-24 | 画像生成装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS62150469A JPS62150469A (ja) | 1987-07-04 |
| JPH0679342B2 true JPH0679342B2 (ja) | 1994-10-05 |
Family
ID=17771323
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60291621A Expired - Fee Related JPH0679342B2 (ja) | 1985-12-24 | 1985-12-24 | 画像生成装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0679342B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02232772A (ja) * | 1989-03-07 | 1990-09-14 | Fujitsu Ltd | Ｌｓｉパターンデータの処理装置 |
| KR101536197B1 (ko) * | 2008-02-27 | 2015-07-13 | 삼성전자주식회사 | 3차원 영상 프로세서 및 프로세싱 방법 |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5490947A (en) * | 1977-12-28 | 1979-07-19 | Matsushita Electric Ind Co Ltd | Signal processor |
-
1985
- 1985-12-24 JP JP60291621A patent/JPH0679342B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPS62150469A (ja) | 1987-07-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2675339B2 (ja) | 色画像情報を決定する方法 | |
| JP3840014B2 (ja) | グラフィックス表示システムの走査変換実施装置 | |
| Baum et al. | Real time radiosity through parallel processing and hardware acceleration | |
| US9842424B2 (en) | Volume rendering using adaptive buckets | |
| US5251322A (en) | Method of operating a computer graphics system including asynchronously traversing its nodes | |
| WO2008037615A1 (en) | Workload distribution in a ray tracing image processing system | |
| US6181346B1 (en) | Graphics system | |
| CN111870953A (zh) | 一种高度图生成方法、装置、设备及存储介质 | |
| JPH0679342B2 (ja) | 画像生成装置 | |
| Dong et al. | Screen Partitioning Load Balancing for Parallel Rendering on a Multi-GPU Multi-Display Workstation. | |
| JP3092131B2 (ja) | 画像生成装置 | |
| Corrie et al. | Parallel volume rendering and data coherence on the fujitsu AP1000 | |
| CA2061054C (en) | Object-based irregular-grid volume rendering | |
| Krogh et al. | Parallel sphere rendering | |
| JPS62269268A (ja) | 画像生成装置 | |
| JP2947984B2 (ja) | マルチプロセッサシステムにおける図形描画方式 | |
| JPS6186876A (ja) | 三次元物体表示処理方式 | |
| Ishii et al. | Cellular array processor CAP and applications | |
| JP3587105B2 (ja) | 図形データ処理装置 | |
| JP2751171B2 (ja) | 画像のシェーディング装置 | |
| JPS63293688A (ja) | 画像生成装置 | |
| WO2004040520A1 (en) | Method and apparatus for providing calligraphic light point display | |
| JP3559336B2 (ja) | Ｃｇデータ作成装置とｃｇアニメーション編集装置 | |
| JP3299010B2 (ja) | 画像生成方法及び画像生成装置 | |
| CN109472854B (zh) | Gpu并行光线跟踪集群的绘制任务动态均衡分配方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |