(57)【要約】      （修正有）【課題】２次元の樹木形状モデルから３次元モデルを自動生成し、３次元モデル編集手段により操作が直感的でデザイナの意図を的確に反映することが可能な３次元樹木形状生成装置を提供する。【解決手段】樹木形状を有した２次元モデルを作成する２次元モデル作成部（２次元モデル作成手段）２と、この樹木形状２次元モデルから、樹木形状を有した３次元モデルを生成する３次元モデル生成部（３次元モデル生成手段）３と、３次元モデルを編集する３次元モデル編集部（３次元モデル編集手段）４と、３次元モデルの枝の切断、削除、又は追加を行う枝編集部（枝編集手段）５と、を備える。【選択図】図１
2005293259.tif 000002
【特許請求の範囲】
【請求項１】
３次元の樹木形状モデルを生成する３次元樹木形状生成装置であって、
樹木形状を有した２次元モデルを作成する２次元モデル作成手段と、該２次元モデル作成手段により作成された樹木形状２次元モデルに基づいて樹木形状を有した３次元モデルを生成する３次元モデル生成手段と、該３次元モデル生成手段により生成された樹木形状３次元モデルに含まれる枝の切断、削除、又は追加を行う枝編集手段と、前記樹木形状３次元モデルを編集する３次元モデル編集手段と、データ入力手段と、前記３次元モデル生成手段の生成結果を出力する生成画像出力手段と、を備えたことを特徴とする３次元樹木形状生成装置。
【請求項２】
前記３次元モデル編集手段は、複数の子枝を指定した親枝に追加する枝繁殖手段と、ユーザが描いた葉の情報に基づいて葉の生え方を選択することにより枝の周囲に葉を生成する葉配列手段と、前記子枝の集合を他の親枝にコピーする枝増殖手段と、を備えていることを特徴とする請求項１に記載の３次元樹木形状生成装置。
【請求項３】
前記枝繁殖手段は、指定した親枝を増加又は減少させる枝繁殖モード編集手段を備え、該枝繁殖モード編集手段は、前記生成画像出力手段に出力された生成画像から前記データ入力手段により指定した親枝をクリック、右回転ジェスチャ、又は左回転ジェスチャすることにより、前記親枝を増加又は減少させることを特徴とする請求項２に記載の３次元樹木形状生成装置。
【請求項４】
前記葉配列手段では、典型的な葉の生え方を前記生成画像出力手段にサムネイル画像として例示し、前記データ入力手段により前記サムネイル画像から必要な画像を選択し、選択したサムネイル画像の枝の周囲に葉を生成することを特徴とする請求項２に記載の３次元樹木形状生成装置。
【請求項５】
前記枝増殖手段は、前記子枝の集合サイズを調整して枝を増殖させるモードと、前記子枝の集合サイズはそのままで葉の数を調整して増殖させるモードとを備えていることを特徴とする請求項２に記載の３次元樹木形状生成装置。
【請求項６】
前記典型的な葉の生え方は、前記枝を中心として左右に葉が一対で生える双生と、前記枝の一方の側に葉が生える互生と、前記枝を中心として左右に葉が複数で生える輪生と、を備えていることを特徴とする請求項４に記載の３次元樹木形状生成装置。
【請求項７】
前記３次元モデル生成手段のアルゴリズムは、全ての枝を地面に投影して得られる２次元距離場を使用し、該２次元距離場に投影された影からの距離値を割り当てることにより前記２次元モデル作成手段により描かれた枝の奥行き情報を計算することを特徴とする請求項１に記載の３次元樹木形状生成装置。
【請求項８】
前記３次元モデル生成手段のアルゴリズムは、前記２次元距離場を使用することにより枝が過度に延びるのを防止するために、前記２次元モデル作成手段により描かれた樹木の２次元形状を囲む２次元凸包を取得し該２次元凸包を押し出して作成した３次元包を用い、解検索の範囲を前記３次元包の内部に絞ること、及び前記枝の長さ及び親枝とその子枝が作る角度に制限を与えること、を前記アルゴリズムの制限とすることを特徴とする請求項１に記載の３次元樹木形状生成装置。
【請求項９】
前記３次元モデル生成手段により生成された３次元モデルの横方向の概観が正面の概観と異なって生成されることを防止するために、前記３次元モデル生成手段のアルゴリズムを適用する範囲を、視線方向のベクトルとなす角度が４５度乃至１３５度とし、該範囲において前記３次元モデル生成手段により３次元モデルを２つ生成した後、一方の３次元モデルを地面から垂直に延びるベクトルの範囲に９０度回転させ、幹を除いて他方の３次元モデルと併合することを特徴とする請求項１に記載の３次元樹木形状生成装置。
【請求項１０】
前記３次元モデル生成手段は、枝１本についての奥行き値を計算するために、前記２次元モデル作成手段により描かれた樹木形状を有した２次元モデルにより枝を表現するストロークを｛ｖｉ｜ｖｉ＝（ｘｉ，ｙｉ，ｚｉ），ｙｉ＝０｝と表現し、ｘ、ｚ集合を入力として受取りそれぞれの点のｙ値を適切に計算するために、３次元空間内では前記ストロークはｚ軸方向に沿って一定の曲率｜（ｄ２ｘ／ｄｚ２）＋（ｄ２ｙ／ｄｚ２）｜を持っていると仮定することを特徴とする請求項１に記載の３次元樹木形状生成装置。
【請求項１１】
請求項１乃至１０の何れか一項に記載の３次元樹木形状生成装置を制御するための３次元樹木形状生成方法をコンピュータが制御可能にプログラミングしたことを特徴とする３次元樹木形状生成プログラム。
【請求項１２】
請求項１１に記載の３次元樹木形状生成プログラムをコンピュータが読み取り可能な形式で記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元樹木形状生成装置に関し、さらに詳しくは、２次元的なスケッチを基にして３次元の樹木形状モデルを生成する３次元樹木形状生成装置と、それを制御するアルゴリズムに関するものである。
【背景技術】
【０００２】
現在の樹木の３次元モデリングは主に２つの手法に基づいている。即ち、１つにはL-systemsに代表される生成規則に基づく手法である。このシステムで生成される樹木モデルやシミュレーションは非常にリアルなものであるが、数式とパラメータ調節はモデリングのためのインターフェースとしては扱いにくく、初心者が気軽に触ってオリジナルの樹木をモデリングできるレベルのものではない。もう１つの手法としては、既存の３次元モデルをそのまま、もしくはパラメータ修正を行って使用するものである。しかし、この手法では３次元樹木モデルのデザインが、与えられたモデルに大きく左右され自由度の高いモデリング環境とは言えなかった。
また、従来例として特開平１１−２３８１４６号公報には、対象樹木をその周囲から複数のカメラで撮影し、得られた画像から背景画像を削除してカラー変換を行なって画像生成用コンピュータに入力し、ボリュームデータを作成するとともに、枝セグメントを作成して樹木モデルを作成し、各部枝セグメントに葉をレンダリングして樹木モデルをディスプレイに表示することにより、実在する樹木形状を近似したモデルの３次元形状を生成する３次元形状生成装置について開示されている。
【特許文献１】特開平１１−２３８１４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、従来のL-systemsの手法においては、数式とパラメータ調節はモデリングのためのインターフェースとしては扱いにくく、初心者が気軽に触ってオリジナルの樹木をモデリングするには難しいといった問題がある。
また既存の３次元モデルを使用する手法では、３次元樹木モデルのデザインが、与えられたモデルに大きく左右され自由度の高いモデリング環境とは言えなかった。
また特許文献１に開示されている従来技術は、複数のカメラが必要となり、システムとして構築するためのコストが高くなるといった問題がある。
本発明は、かかる課題に鑑み、２次元の樹木形状モデルから３次元モデルを自動生成し、３次元モデル編集手段により操作が直感的でデザイナの意図を的確に反映することが可能な３次元樹木形状生成装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
本発明はかかる課題を解決するために、請求項１は、３次元の樹木形状モデルを生成する３次元樹木形状生成装置であって、樹木形状を有した２次元モデルを作成する２次元モデル作成手段と、該２次元モデル作成手段により作成された樹木形状２次元モデルに基づいて樹木形状を有した３次元モデルを生成する３次元モデル生成手段と、該３次元モデル生成手段により生成された樹木形状３次元モデルに含まれる枝の切断、削除、又は追加を行う枝編集手段と、前記樹木形状３次元モデルを編集する３次元モデル編集手段と、データ入力手段と、前記３次元モデル生成手段の生成結果を出力する生成画像出力手段と、を備えたことを特徴とする。
本発明の最も大きな特徴は、樹木形状を有した２次元モデルから３次元の樹木形状モデルを生成する点である。そして、枝編集手段により枝の切断、削除、又は追加を行い、更に複雑な編集を行うために３次元モデル編集手段により樹木を編集してユーザが希望する樹木形状に近づけるものである。それを実現するために、編集データを入力するデータ入力手段と、３次元の樹木形状モデルをモニタに表示する生成画像出力手段とを備えている。尚、樹木形状とは樹木、草、花、海草、その他の自然物、人間の創造物等であって樹木に似た形状を備えた物を全てを含む。
かかる発明によれば、樹木形状を有した２次元モデルを作成する２次元モデル作成手段と、この２次元モデル作成手段により作成された樹木形状２次元モデルに基づいて樹木形状を有した３次元モデルを生成する３次元モデル生成手段と、この３次元モデル生成手段により生成された樹木形状３次元モデルに含まれる枝の切断、削除、又は追加を行う枝編集手段と、樹木形状３次元モデルを編集する３次元モデル編集手段と、データ入力手段と、３次元モデル生成手段の生成結果を出力する生成画像出力手段と、を備えたので、ユーザによる操作が直感的でデザイナの意図を的確に反映することが可能な３次元樹木形状生成装置を提供することができる。
【０００５】
請求項２は、前記３次元モデル編集手段は、複数の子枝を指定した親枝に追加する枝繁殖手段と、ユーザが描いた葉の情報に基づいて葉の生え方を選択することにより枝の周囲に葉を生成する葉配列手段と、前記子枝の集合を他の親枝にコピーする枝増殖手段と、を備えていることを特徴とする。
２次元モデルから３次元モデルを生成する作業は自動的に行われる。しかし、その３次元モデルは幹と親枝から構成され、樹木形状としては未完成である。そこで本発明では３次元モデル編集手段を備え、これにより枝を繁殖させたり、その枝の周囲に葉を生成したり、子枝の集合を親枝にコピーして枝を増殖したりすることができる。
かかる発明によれば、３次元モデル編集手段は、複数の子枝を指定した親枝に追加する枝繁殖手段と、ユーザが描いた葉の情報に基づいて葉の生え方を選択することにより枝の周囲に葉を生成する葉配列手段と、子枝の集合を他の親枝にコピーする枝増殖手段と、を備えているので、直感的な操作でデザイナの意図を的確に３次元モデルに反映することができる。
請求項３は、前記枝繁殖手段では、指定した親枝を増加又は減少させる枝繁殖モード編集手段を備え、該枝繁殖モード編集手段は、前記生成画像出力手段に出力された生成画像から前記データ入力手段により指定した親枝をクリック、右回転ジェスチャ、又は左回転ジェスチャすることにより、前記親枝を増加又は減少させることを特徴とする。
複数の子枝を指定した親枝に追加する枝繁殖手段では、繁殖の操作が容易であることが重要である。そこで本発明では、データ入力手段、例えばマウスにより繁殖させたい親枝をクリックしたり、右回転ジェスチャ、又は左回転ジェスチャすることにより、簡単に親枝を増減させることができる。
かかる発明によれば、枝繁殖手段では、指定した親枝を増加又は減少させる枝繁殖モード編集手段を備え、この枝繁殖モード編集手段は、生成画像出力手段に出力された生成画像からデータ入力手段により指定した親枝をクリック、右回転ジェスチャ、又は左回転ジェスチャすることにより、親枝を増加又は減少させることができるので、操作性が向上し編集操作のスピードアップを図ることができる。
【０００６】
請求項４は、前記葉配列手段では、典型的な葉の生え方を前記生成画像出力手段にサムネイル画像として例示し、前記データ入力手段により前記サムネイル画像から必要な画像を選択し、選択したサムネイル画像の枝の周囲に葉を生成することを特徴とする。
ユーザが描いた葉の情報に基づいて葉の生え方を選択することにより枝の周囲に葉を生成する葉配列手段では、典型的な葉の生え方をモニタ上にサムネイル画像として表示する。ユーザはそのサムネイル画像から必要な画像を選択すると、その葉の生え方に基づいた葉を枝の周囲に生成することができる。
かかる発明によれば、葉配列手段では、典型的な葉の生え方を生成画像出力手段にサムネイル画像として例示し、データ入力手段によりサムネイル画像から必要な画像を選択し、選択したサムネイル画像の枝の周囲に葉を生成するので、ユーザは容易に典型的な葉の生え方に基づいて葉を生成することができる。
請求項５は、前記枝増殖手段では、前記子枝の集合サイズを調整して枝を増殖させるモードと、前記子枝の集合サイズはそのままで葉の数を調整して増殖させるモードとを備えていることを特徴とする。
子枝の集合を他の親枝にコピーする枝増殖手段では、２種類のモードがある。１つは子枝の集合サイズを調整して枝を増殖させるモードである。これは子枝のサイズが枝ごとに異なるように増殖させることができる。他の１つは子枝の集合サイズはそのままで葉の数を調整して増殖させるモードである。これは全て同じサイズの子枝の集合として増殖させることができる。
かかる発明によれば、枝増殖手段では、子枝の集合サイズを調整して枝を増殖させるモードと、子枝の集合サイズはそのままで葉の数を調整して増殖させるモードとを備えているので、バラエティに富んだ枝を増殖させることができる。
【０００７】
請求項６は、前記典型的な葉の生え方は、前記枝を中心として左右に葉が一対で生える双生と、前記枝の一方の側に葉が生える互生と、前記枝を中心として左右に葉が複数で生える輪生と、を備えていることを特徴とする。
典型的な葉の生え方には３種類有り、双生、互生、及び輪生がある。ユーザはこの３種類の葉の生え方から任意に選択して枝に葉を生えさせることができる。
かかる発明によれば、典型的な葉の生え方は、枝を中心として左右に葉が一対で生える双生と、枝の一方の側に葉が生える互生と、枝を中心として左右に葉が複数で生える輪生と、を備えているので、樹木の種類により最適な葉の生え方を選択することができる。
請求項７は、前記３次元モデル生成手段のアルゴリズムは、全ての枝を地面に投影して得られる２次元距離場を使用し、該２次元距離場に投影された影からの距離値を割り当てることにより前記２次元モデル作成手段により描かれた枝の奥行き情報を計算することを特徴とする。
本発明のアルゴリズムは、２次元スケッチで描かれた枝の奥行き情報を計算するためのものであり、計算結果の３次元モデルは、あらゆる角度から見たときに同じような概観になるのが目標である。即ち、１本の枝に対する基本的な戦略は、その枝と他の枝との距離がなるべく大きくなるように、その枝の位置を決定しようというものである。従って、理想的には３次元ボリュームを作成し、それぞれのボクセルは最も近い枝への距離を保存するような距離場（ディスタンスフィールド）を内部的に持つべきであるが、枝１本１本の処理ごとに３次元距離場を更新するのは、非常に計算時間がかかる。そこで本発明では、全ての枝を地面に投影したような２次元距離場を使用する。そしてこの２次元距離場に投影された影からの距離値を割り当てることにより、２次元モデル作成手段により描かれた枝の奥行き情報を計算するものである。
かかる発明によれば、３次元モデル生成手段のアルゴリズムは、全ての枝を地面に投影して得られる２次元距離場を使用し、この２次元距離場に投影された影からの距離値を割り当てることにより、２次元モデル作成手段により描かれた枝の奥行き情報を計算するので、計算時間を短縮することができる。
【０００８】
請求項８は、前記３次元モデル生成手段のアルゴリズムは、前記２次元距離場を使用することにより枝が過度に延びるのを防止するために、前記２次元モデル作成手段により描かれた樹木の２次元形状を囲む２次元凸包を取得し該２次元凸包を押し出して作成した３次元包を用い、解検索の範囲を前記３次元包の内部に絞ること、及び前記枝の長さ及び親枝とその子枝が作る角度に制限を与えること、を前記アルゴリズムの制限とすることを特徴とする。
２次元距離場を用いるだけでは、枝が奥行き方向に過度に延びてしまうという現象を押さえられない。これは無限の長さを持つ枝が、最も他の枝との距離を大きくとっていると判定されてしまうからである。これを防ぐために、２次元スケッチを囲む２次元凸包を得て、その凸包を押し出して作成した３次元包を用いる。そして解検索の範囲をこの３次元包の内部だけに絞る。また他の制約として、枝の長さ、接続する枝同士が作る角度を与え、自然な樹木が得られるようにアルゴリズムを設計する。
かかる発明によれば、３次元モデル生成手段のアルゴリズムは、２次元距離場を使用することにより枝が過度に延びるのを防止するために、２次元モデル作成手段により描かれた樹木の２次元形状を囲む２次元凸包を取得し、この２次元凸包を押し出して作成した３次元包を用い、解検索の範囲を３次元包の内部に絞ること、及び枝の長さ及び親枝とその子枝が作る角度に制限を与えること、をアルゴリズムの制限とすることにより枝が過度に延びるのを防止することができる。
【０００９】
請求項９は、前記３次元モデル生成手段により生成された３次元モデルの横方向の概観が正面の概観と異なって生成されることを防止するために、前記３次元モデル生成手段のアルゴリズムを適用する範囲を、視線方向のベクトルとなす角度が４５度乃至１３５度とし、該範囲において前記３次元モデル生成手段により３次元モデルを２つ生成した後、一方の３次元モデルを地面から垂直に延びるベクトルの範囲に９０度回転させ、幹を除いて他方の３次元モデルと併合することを特徴とする。
樹木の２次元スケッチを描く際、ユーザは横方向に広がる枝を描くのみで、前後方向に広がる枝を省略する傾向がある。しかし、上で述べたアルゴリズムは、２次元スケッチを全ての方向に一様に広げようとするため、結果としての３次元樹木モデルは、正面の概観は保たれるが、横方向から見た場合の概観が２次元スケッチと大きく違ってしまうという問題がある。この問題を解決するために、実際に前後方向に伸びる枝はシステムが自動的に追加することにする。その方法は、アルゴリズムを拡張するにあたって、アルゴリズムを適用する範囲は、視線方向のベクトルとなす角度が４５度から１３５度までとする。この範囲で３次元樹木を２つ作成した後に、一方を地面から垂直に伸びるベクトルの周囲に９０度回転させて、幹を除いてもう一方とマージする。
かかる発明によれば、前記３次元モデル生成手段のアルゴリズムを適用する範囲を、視線方向のベクトルとなす角度が４５度から１３５度とし、この範囲において３次元モデル生成手段により３次元モデルを２つ生成した後、一方の３次元モデルを地面から垂直に延びるベクトルの範囲に９０度回転させ、幹を除いて他方の３次元モデルと併合するので、３次元モデル生成手段により生成された３次元モデルの横方向の概観が正面の概観と異なって生成されることを防止することができる。
【００１０】
請求項１０は、前記３次元モデル生成手段は、枝１本についての奥行き値を計算するために、前記２次元モデル作成手段により描かれた樹木形状を有した２次元モデルにより枝を表現するストロークを｛ｖｉ｜ｖｉ＝（ｘｉ，ｙｉ，ｚｉ），ｙｉ＝０｝と表現し、ｘ、ｚ集合を入力として受取りそれぞれの点のｙ値を適切に計算するために、３次元空間内では前記ストロークはｚ軸方向に沿って一定の曲率｜（ｄ２ｘ／ｄｚ２）＋（ｄ２ｙ／ｄｚ２）｜を持っていると仮定することを特徴とする。
実際の樹木の枝を見た場合、形を変えずに平面上に投影させることのできる枝はめったにない。例えば、波打つような形状をした枝を見た場合、その枝は横から眺めてみても同様に波打つような形状をしているものである。本発明ではこの効果を与えるために、枝の奥行き方向を計算するためのアルゴリズムを実装した。即ち、元の２次元スケッチで、枝を表現するストロークは３次元点集合として表現されているが、２次元であるので、全てのｙ値（奥行き値）は０となっている（｛ｖｉ｜ｖｉ＝（ｘｉ，ｙｉ，ｚｉ），ｙｉ＝０｝）。またｚ軸方向をストロークの始点から終点へのベクトルとして、ｘ、ｚ値集合を入力として受け取り、それぞれの点のｙ値を適切に計算し出力する。ｙ値を計算するために、３次元空間内ではストロークはｚ軸方向に沿って一定の曲率を持っていると仮定する（｜（ｄ２ｘ／ｄｚ２）＋（ｄ２ｙ／ｄｚ２）｜）。この式を解くことでｙ値を計算することができる。
かかる発明によれば、３次元モデル生成手段は、枝１本についての奥行き値を計算するために、２次元モデル作成手段により描かれた樹木形状を有した２次元モデルにより枝を表現するストロークを｛ｖｉ｜ｖｉ＝（ｘｉ，ｙｉ，ｚｉ），ｙｉ＝０｝と表現し、ｘ、ｚ集合を入力として受取りそれぞれの点のｙ値を適切に計算するために、３次元空間内ではストロークはｚ軸方向に沿って一定の曲率｜（ｄ２ｘ／ｄｚ２）＋（ｄ２ｙ／ｄｚ２）｜を持っていると仮定するので、枝１本についての奥行き値を簡単に計算することができる。
請求項１１は、請求項１乃至１０の何れか一項に記載の３次元樹木形状生成装置を制御するための３次元樹木形状生成方法をコンピュータが制御可能にプログラミングしたことを特徴とする。
かかる発明によれば、本発明の３次元樹木形状生成方法をコンピュータが制御可能なＯＳに従ってプログラミングすることにより、そのＯＳを備えたコンピュータであれば同じ処理方法により制御することができる。
請求項１２は、請求項１１に記載の３次元樹木形状生成プログラムをコンピュータが読み取り可能な形式で記録したことを特徴とする。
かかる発明によれば、３次元樹木形状生成プログラムをコンピュータが読み取り可能な形式で記録媒体に記録することにより、この記録媒体を持ち運ぶことにより何処でもプログラムを稼動することができる。
【発明の効果】
【００１１】
請求項１の発明によれば、樹木形状を有した２次元モデルを作成する２次元モデル作成手段と、この２次元モデル作成手段により作成された樹木形状２次元モデルに基づいて樹木形状を有した３次元モデルを生成する３次元モデル生成手段と、この３次元モデル生成手段により生成された樹木形状３次元モデルに含まれる枝の切断、削除、又は追加を行う枝編集手段と、樹木形状３次元モデルを編集する３次元モデル編集手段と、データ入力手段と、３次元モデル生成手段の生成結果を出力する生成画像出力手段と、を備えたので、ユーザによる操作が直感的でデザイナの意図を的確に反映することが可能な３次元樹木形状生成装置を提供することができる。
また請求項２では、３次元モデル編集手段は、複数の子枝を指定した親枝に追加する枝繁殖手段と、ユーザが描いた葉の情報に基づいて葉の生え方を選択することにより枝の周囲に葉を生成する葉配列手段と、子枝の集合を他の親枝にコピーする枝増殖手段と、を備えているので、直感的な操作でデザイナの意図を的確に３次元モデルに反映することができる。
また請求項３では、枝繁殖手段では、指定した親枝を増加又は減少させる枝繁殖モード編集手段を備え、この枝繁殖モード編集手段は、生成画像出力手段に出力された生成画像からデータ入力手段により指定した親枝をクリック、右回転ジェスチャ、又は左回転ジェスチャすることにより、親枝を増加又は減少させることができるので、操作性が向上し編集操作のスピードアップを図ることができる。
【００１２】
また請求項４では、葉配列手段では、典型的な葉の生え方を生成画像出力手段にサムネイル画像として例示し、データ入力手段によりサムネイル画像から必要な画像を選択し、選択したサムネイル画像の枝の周囲に葉を生成するので、ユーザは容易に典型的な葉の生え方に基づいて葉を生成することができる。
また請求項５では、枝増殖手段では、子枝の集合サイズを調整して枝を増殖させるモードと、子枝の集合サイズはそのままで葉の数を調整して増殖させるモードとを備えているので、バラエティに富んだ枝を増殖させることができる。
また請求項６では、典型的な葉の生え方は、枝を中心として左右に葉が一対で生える双生と、枝の一方の側に葉が生える互生と、枝を中心として左右に葉が複数で生える輪生と、を備えているので、樹木の種類により最適な葉の生え方を選択することができる。
また請求項７では、３次元モデル生成手段のアルゴリズムは、全ての枝を地面に投影して得られる２次元距離場を使用し、この２次元距離場に投影された影からの距離値を割り当てることにより、２次元モデル作成手段により描かれた枝の奥行き情報を計算するので、計算時間を短縮することができる。
また請求項８では、３次元モデル生成手段のアルゴリズムは、２次元距離場を使用することにより枝が過度に延びるのを防止するために、２次元モデル作成手段により描かれた樹木の２次元形状を囲む２次元凸包を取得し、この２次元凸包を押し出して作成した３次元包を用い、解検索の範囲を３次元包の内部に絞ること、及び枝の長さ及び親枝とその子枝が作る角度に制限を与えること、をアルゴリズムの制限とすることにより枝が過度に延びるのを防止することができる。
【００１３】
また請求項９では、前記３次元モデル生成手段のアルゴリズムを適用する範囲を、視線方向のベクトルとなす角度が４５度から１３５度とし、この範囲において３次元モデル生成手段により３次元モデルを２つ生成した後、一方の３次元モデルを地面から垂直に延びるベクトルの範囲に９０度回転させ、幹を除いて他方の３次元モデルと併合するので、３次元モデル生成手段により生成された３次元モデルの横方向の概観が正面の概観と異なって生成されることを防止することができる。
また請求項１０では、３次元モデル生成手段は、枝１本についての奥行き値を計算するために、２次元モデル作成手段により描かれた樹木形状を有した２次元モデルにより枝を表現するストロークを｛ｖｉ｜ｖｉ＝（ｘｉ，ｙｉ，ｚｉ），ｙｉ＝０｝と表現し、ｘ、ｚ集合を入力として受取りそれぞれの点のｙ値を適切に計算するために、３次元空間内ではストロークはｚ軸方向に沿って一定の曲率｜（ｄ２ｘ／ｄｚ２）＋（ｄ２ｙ／ｄｚ２）｜を持っていると仮定するので、枝１本についての奥行き値を簡単に計算することができる。
また請求項１１では、本発明の３次元樹木形状生成方法をコンピュータが制御可能なＯＳに従ってプログラミングすることにより、そのＯＳを備えたコンピュータであれば同じ処理方法により制御することができる。
また請求項１２では、３次元樹木形状生成プログラムをコンピュータが読み取り可能な形式で記録媒体に記録することにより、この記録媒体を持ち運ぶことにより何処でもプログラムを稼動することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明を図に示した実施形態を用いて詳細に説明する。但し、この実施形態に記載される構成要素、種類、組み合わせ、形状、その相対配置などは特定的な記載がない限り、この発明の範囲をそれのみに限定する主旨ではなく単なる説明例に過ぎない。
図１は本発明の実施形態に係る３次元樹木形状生成装置のシステム構成を示すブロック図である。この３次元樹木形状生成装置１００は、基本構成としてパーソナルコンピュータ（ＰＣ）１により構成され、その制御はＰＣ１が有するメモリに格納されたプログラムに従って制御される。そしてＰＣ１は樹木形状を有した２次元モデルを作成する２次元モデル作成部（２次元モデル作成手段）２と、この２次元モデル作成部２により作成された樹木形状２次元モデルから、樹木形状を有した３次元モデルを生成する３次元モデル生成部（３次元モデル生成手段）３と、樹木形状の３次元モデルを編集する３次元モデル編集部（３次元モデル編集手段）４と、３次元モデル生成部３により生成された３次元モデルの枝の切断、削除、又は追加を行う枝編集部（枝編集手段）５と、外部のインターフェースに２次元モデル作成部２及び３次元モデル編集部４のデータを入力するマウス６、ペンタブレット７、及びキーボード８（データ入力手段）と、３次元モデル生成部３による生成結果を出力するモニタ（生成画像出力手段）９と、を備えて構成される。
図２は３次元樹木モデルをデザインする際の典型的な流れを示す図である。図１を参照して説明する。まずユーザはシンプルな２次元樹木１０を、例えばペンタブレット７によりスケッチする（２次元スケッチ）。スケッチを終え、モニタ９上の画面に表示された３次元ボタン（図示せず）を押すことにより、３次元モデル生成部３が２次元スケッチから３次元樹木モデル１１を自動的に生成する（自動３次元生成：詳細は後述する）。次にユーザはモニタ９上の画面に表示された例えば「Ｅｄｉｔ」ボタン（図示せず）を押すことにより、枝編集モードに移り、枝編集部５により符号１２に示すようにジェスチャ入力により枝を切断、消去したり、また新たな枝を追加することができる（枝繁殖手段）。ユーザはまた、３次元モデル編集部４による編集モードを用いることで符号１３（葉配列手段）、符号１４（枝増殖手段）のように、より複雑な樹木形状を作成することができる（詳細は後述する）。
【００１５】
図３は図２で説明した枝繁殖モード（Branch Multiplicationモード）について説明する図である。図３（ａ）は３次元樹木モデルを表す図であり、幹２１に複数の親枝２０が生成され、その影２２が描かれている。図３（ｂ）は枝繁殖モードにより子枝が繁殖した図である。枝繁殖モードでは、ユーザはより多くの子枝２３を、指定した親枝２０に追加することができる。この図では矢印２４により指定した親枝２０ａをクリックして子枝２３を増加させるか、右回転ジェスチャで子枝を増加、左回転ジェスチャで子枝を減少させるというインターフェースを実装してある。
図４は図２で説明した葉配列モード（Leaf Arrangementモード）について説明する図である。図４（ａ）はモニタ９にユーザが描いた葉２６の情報を基に、サムネイル２７を例示した図であり、図４（ｂ）は選択されたサムネイルに葉を生やした図である。この葉配列モードでは、典型的な葉の生え方、例えば枝を中心として左右に葉が一対で生える双生２７ａ、枝の一方の側に葉が生える互生２７ｂ、枝を中心として左右に葉が複数で生える輪生２７ｃをシステムがサムネイル２７として例示し、ユーザがそこから選択することで、枝の周囲に葉を生成することができる。例えば、ユーザが輪生２７ｃを選択した場合、マウス６により画面上のサムネイルをクリックするたびに、２７ｇのように枝の周囲に葉が輪生して生成されるようにしてもよい。
【００１６】
図５は図２で説明した枝増殖モード（Branch Propagationモード）について説明する図である。この枝増殖モードでは、子枝集合３１を他の親枝３０にコピーすることで、全体的に茂った樹木を生成することができる。このモードでは、図５（ａ）のように子枝集合３１を子枝集合３２のように葉のサイズを小さく調整して伝播させるものと、図５（ｂ）のように子枝集合３１の葉のサイズはそのままにして、子枝集合３３のように葉の数を調整して伝播させるものとがある。
図６は図２で説明した３次元樹木モデルをデザインする際の、更に詳細な全体的な流れを示すフローチャートである。まず、ユーザがペンタブレット７等で２次元樹木をスケッチする。そしてこの２次元樹木を「tree2D」とする（Ｓ１）。この「tree2D」をコピーして「tree2D-a」、「tree2D-b」とする（Ｓ２）。次に「tree2D-a」及び「tree2D-b」に３次元モデル生成部３により、３次元化アルゴリズム（詳細は後述する）を適用して３次元モデルを生成する（Ｓ３）。次に「tree2D」の全ての枝に枝１本についての奥行き値計算（詳細は後述する）を適用した結果で「tree2D-a」の枝を置換する（Ｓ４）。同じく「tree2D」の全ての枝に枝１本についての奥行き値計算を適用した結果で「tree2D-b」の枝を置換する（Ｓ５）。そして「tree2D-b」を９０度回転させて「tree2D-a」とマージし「tree3D」とする（基本アルゴリズムの拡張：詳細は後述する）（Ｓ６）。そして「tree3D」を結果としてモニタ９に出力する（Ｓ７）。
【００１７】
次に図６により説明したフローチャートに記載された「奥行き値計算」について図８を参照して説明する。実際の樹木の枝を見た場合、形を変えずに平面上に投影させることのできる枝はめったにない。例えば、波打つような形状をした枝を見た場合、その枝は横から眺めてみても同様に波打つような形状をしているものである。この効果を与えるために、本発明では枝の奥行き方向を計算するためのアルゴリズムを実装した。このアルゴリズムは、枝は３次元空間内で一定の曲率を持っていると仮定することで達成される。例えば図８のように、ユーザがサインカーブ３５を枝としてスケッチした場合、システムは結果を螺旋形状３６として出力することになる。
ｓｔｒｏｋｅ＝｛ｖｉ｜ｖｉ＝（ｘｉ，ｙｉ，ｚｉ），ｙｉ＝０｝・・・（１）
｜（ｄ２ｘ／ｄｚ２）＋（ｄ２ｙ／ｄｚ２）｜＝ｃｏｎｓｔ・・・・・・（２）
更にアルゴリズムの詳細を説明すると、元の２次元スケッチ（サインカーブ３５）で、枝を表現するストロークは３次元点集合として表現されているが、２次元であるので、（１）式の全てのｙ値（奥行き値）は０となっている。ｚ軸方向をストロークの始点から終点へのベクトルとしてとる。また本発明のアルゴリズムはｘ、ｚ値集合を入力として受け取り、それぞれの点のｙ値を適切に計算し出力する。ｙ値を計算するために、（２）式のように３次元空間内ではストロークはｚ軸方向に沿って一定の曲率を持っていると仮定する。この（１）式、（２）式を解くことでｙ値を計算することができる。まず一定な曲率を決める。この値はｚ軸方向のｘｉにおける２階微分の絶対値の最大値とする。この値とｘｉにおけるｘの２階微分が得られれば、上式を用いてｙｉにおけるｙの２階微分を計算することができる。
次に、それぞれのｙの２階微分値について、その符号を決定する。最終的に螺旋形状を得るためには、それぞれの符号はｚ軸に沿ってｘの１階微分値が０となるところで変化する、と考えて決定することができる。またｙのｙｉにおける２階微分値の絶対値と符号が決定されれば、積分を２回行うことにより、ｙｉの値を計算することができる。ｙの最初の値を０とし、最後のｙの１階微分値が０となるように、ｙの最初の１階微分の値を調節する。
【００１８】
次に図６により説明したフローチャートに記載された「基本アルゴリズムの拡張」について図１０、１１、１２を参照して説明する。図１０のように樹木の２次元スケッチ４０を描く際、ユーザは横方向に広がる枝を描くのみで、前後方向に広がる枝を省略する傾向がある。しかし前述した基本アルゴリズムは、２次元スケッチを全ての方向に一様に広げようとするため、結果の３次元樹木モデル４１は正面の概観は保たれるが、横方向から見た場合の概観４２が２次元スケッチ４０と大きく違ってしまうという問題がある。この問題を解決するために、ユーザは横方向に広がる枝のみを描く、という過程をおいてアルゴリズムを拡張し、実際に前後方向に伸びる枝はシステムが自動的に追加することにする。
またアルゴリズムを拡張するにあたって、本発明のアルゴリズムを適用する範囲は、視線方向のベクトルとなす角度が４５度から１３５度までとする。この範囲で図１１のように２次元スケッチ４５から３次元樹木４６、４７を２つ作成した後に、３次元樹木４７を地面から垂直に伸びるベクトルの周囲に９０度回転させて（符号４８）、幹を除いて３次元樹木４６とマージして３次元樹木４９を得る。
その結果図１２のように２つの３次元樹木５１、５２は、本発明のアルゴリズムのランダム性から少しずつ異なる樹木になっている。この、単純でアドホックなトリックは、非常に上手く働いており、本発明のシステムでは欠かすことのできないアルゴリズムである。
図７は本発明の３次元アルゴリズムの基本フローチャートである。まず２次元ディスタンスフィールド（２次元距離場）を初期化してこれを「2DdistanceField」とする（詳細は後述する）。そして２Ｄ凸包を計算し、更に３Ｄ包を計算して（詳細は後述する）これを3DHullとする（Ｓ１１）。次に幹からスタートして末端の枝に向かって順に処理して、処理終了か否かをチェックする（Ｓ１２）。チェックの結果、処理が終了したら（Ｓ１２でＮＯのルート）、処理を終了する（Ｓ１５）。ステップＳ１２で処理が未終了であれば（Ｓ１２でＹＥＳのルート）、処理する枝をBranchとして、Branchとその親枝が作る角度、Branchの長さ、及び3DHullの内部に収まる必要性のこれら３つの制限を加えながら「2DdistanceField」内で最も広い場所に落ち着くようにBranchのｚ値を決定する（詳細は後述する）（Ｓ１３）。そして「2DdistanceField」を更新して（Ｓ１４）ステップＳ１２に戻って繰り返す。
【００１９】
次に図７により説明したフローチャートに記載された「2DdistanceField：２次元距離場」について図１３を参照して説明する。２次元ディスタンスフィールドとは距離場とも言い２次元配列のことである。説明を簡略化するために、例えば将棋板で説明すると、ゲーム開始時の将棋板を考えると王という駒への距離というものが全てのマスに定義できる。即ち、王がいる場所は０で、金がいる場所を１とすると、金の前のあいているマスの値はルート２とすることができる。そして味方の香車のマスには４と書き込める。また相手の王のいるマスには８と書き込める。このように全てのマスに王からの距離値を定義することができる。
このように考えると、図１３（Ａ）、（Ｂ）の（ａ）に図示された樹木５５に上から光を当てると、図１３（ｂ）のように地面に影５７、５９ができる。地面の影５７、５９は２次元画像である。そしてこの２次元画像の各マスに、この影からの距離値を割り当ててやって、できた２次元配列が２次元ディスタンスフィールドとなる。即ち、図１３（Ａ）の（ａ）は枝が７本の状態である（１本の枝は幹の影で見えない）。それを地面に投影してできた２次元ディスタンスフィールドを図１３（Ａ）の（ｂ）に示す。黒い部分が距離０で、白くなるにつれてマスに割り当ててある距離値が大きくなっているとすると、図１３（Ａ）の（ｂ）を見ると右下５７ａに白い部分が目立つ。この部分は影までの距離値が大きい、つまり広く空いている領域となるので、ここに次の枝５８を割り当てて埋めた結果が図１３（Ｂ）の（ｂ）の符号５９ａとなる。
言い換えると、図１３（Ａ）の（ａ）では矢印５６を除いて７本の枝が描かれている。これらの枝は全てｚ値が割り当てられていて、それを２次元ディスタンスフィールドに投影すると、図１３（Ａ）の（ｂ）のように見えていたと仮定する。そして矢印５６は次にｚ値を割り当てるための、まだ２次元の（ｚ値が全て０の）枝であるとして、この矢印５６にｚ値を割り当てた結果、図１３（Ｂ）の（ｂ）の図ができる。つまり図１３（Ｂ）の（ｂ）では枝は８本、そして、ディスタンスフィールドの「もっとも広かった位置」５７ａに枝５８が収まって影５９ａになるという図である。
【００２０】
次に図７により説明したフローチャートに記載されたステップＳ１３の処理について図９を参照して説明する。ここで述べるアルゴリズムは、２次元スケッチで描かれた枝の奥行き情報を計算するためのものである。計算結果の３次元モデルは、あらゆる角度から見たときに同じような概観を表現するようになるのが目標である。そして１本の枝に対する基本的な戦略は、その枝と他の枝との距離がなるべく大きくなるように、枝の位置を決定しようというものである。この場合、樹木の形状には最適解が存在するはずであるが、本発明に係る３次元樹木形状生成装置が備えるアルゴリズムでは、そのような最適解を求めるのではなく、枝１つ１つに対して順番に処理を施していく。即ち、２次元スケッチを幹をルートとする木構造だとすると、幹からより若い世代へ処理を施していき、同じ世代間の処理順序はランダムであるとする。理想的には、３次元ボリュームを作成し、それぞれのボクセルは最も近い枝への距離を保存するようなディスタンスフィールドを内部的に持つべきである。しかし、枝１本１本の処理ごとに３次元ディスタンスフィールドを更新していくのは非常に計算時間がかかるため、ここでは、全ての枝を地面に投影したような、図１３で説明した２次元ディスタンスフィールドを使用することにした。本発明の実装では１２８ｘ１２８のディスタンスフィールドを用い、全解検索を行っている。
しかし、ディスタンスフィールドを用いるだけでは、枝１本が奥行き方向に過度に延びてしまうという現象を押さえ込むことができない。なぜなら無限の長さを持つ枝が、もっとも他の枝との距離を大きくとっていると判定されてしまうからである。これを防ぐために、図９に示すように２次元スケッチ６０を囲む２次元凸包６１（２次元スケッチ６０のスケッチを取り囲む多角形で、必ず凸になる）を得て、その凸包を押し出して作成した３次元包６２（この２次元凸包を３次元に膨らませることにより生成する）を用いる。そして解検索の範囲をこの３次元包６２の内部だけに絞るのである。押し出しは２次元凸包６１の最下点Ａから最上点Ｂにかけて行い、結果の３次元包６２はルート２倍に拡大したものを用いる。この拡大処理は２次元凸包６１に接している枝が前後に広がる自由を与えるために必要な処理である。
【００２１】
本発明のアルゴリズムは枝の長さにも制限を与える。これはある枝の長さは、その親枝よりも短い、という経験則に基づく。ここではWeber and Pennによって１９９５年に提案された論文「Creation and Rendering of Realistic Trees. In Proceedings of ACM SIGGRAPH 95， 119-128」にある式を用いて長さを制限した。この長さの制限も、２次元から３次元に膨らむためのリラクゼーションとして、１．２の倍率で拡大して用いる。即ち、長さについても同様で、２次元スケッチを３次元樹木に拡張すると、かならず枝は長くなるが、その長くなり具合にも程度というものがあると考え、この“程度”を２次元スケッチから計算し制約として用いる。
また本発明のアルゴリズムは更に、親枝とその子枝が作る角度にも制限を与える。まず２次元スケッチに対して、親枝とその全ての子枝とが作る角度（Down angle）の最大値を求める。その最大値を１．２倍して、その値を３次元になった際にも、その親枝と子枝間で作られる角度の最大値とする。即ち、図１４に示すように例えば実際の樹木を見たときに、親の枝７１から生える子枝７２を見ると、その親枝７１との間の角度（Down angle）βは、ある程度の制限がある。この“制限”をユーザが描いた樹木のスケッチから計算し、３次元樹木を作るときにも、その角度以上は広がらないようにするのがこのアルゴリズムである。
そして以上のプロセスを全ての枝に行う。なお以上のプロセスを行うにあたって、枝は全て始点と終点を結ぶ１セグメントから成る線分として扱われる。これは単純化と効率化のためである。線分から成る２次元スケッチを３次元に広げた後、オリジナルの２次元スケッチの枝ストロークに、対応する線分をもとに図８で説明した奥行き情報を与える。
（実施例）
【００２２】
図１５は本発明の３次元樹木形状生成装置によりモデリングした３次元樹木モデルの実際の図である。図１５（Ａ）は発明者がモデリングした３次元樹木モデルの図である、このモデリングでは（ａ）イチョウ、（ｂ）マツ、（ｃ）アメリカヌマミズキ、（ｄ）カエデ、（ｅ）オリエントブナ、（ｆ）モミ、（ｇ）カバ、（ｈ）マツ、（ｉ）サクラ、（ｊ）ヨーロッパハイマツ、（ｋ）イチョウ、（ｌ）エノキが生成され、各々の３次元樹木モデルは平均して１０分以内のモデリング時間であった。そして広葉樹モデルは主に２次元スケッチを３次元化し、枝と葉の伝播機能を使うことでモデリングできた。また、枝繁殖モードは針葉樹をモデリングする際に便利であることが分かった。
また本発明の３次元樹木形状生成装置の有用性を調べるために、ユーザテストを行った。被験者は７名、いずれも提案システムの操作に関しては初心者である。図１５（Ｂ）は被験者がデザインした３次元樹木モデルと、モデリングに要した時間である。ここに掲載した樹木モデルのいくつかは、独特ではあるが、自然の樹木と比べると不自然だと思われるものがある。しかし、このような樹木こそユーザの意図をより反映しており、既存の生成規則に基づく手法や、モデリングライブラリを用いる手法などではデザインすることが難しかったものであると言える。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態に係る３次元樹木形状生成装置のシステム構成を示すブロック図。
【図２】３次元樹木モデルをデザインする際の典型的な流れを示す図。
【図３】図２で説明した枝繁殖モードについて説明する図。
【図４】図２で説明した葉配列モードについて説明する図。
【図５】図２で説明した枝増殖モードについて説明する図。
【図６】図２で説明した３次元樹木モデルをデザインする際の、更に詳細な全体的な流れを示すフローチャート。
【図７】本発明の３次元アルゴリズムの基本フローチャート。
【図８】図６により説明したフローチャートに記載された「奥行き値計算」について説明する図。
【図９】図７により説明したフローチャートに記載されたステップＳ１３の処理について説明する図。
【図１０】アルゴリズムの拡張を説明する図（その１）。
【図１１】アルゴリズムの拡張を説明する図（その２）。
【図１２】アルゴリズムの拡張を説明する図（その３）。
【図１３】図７により説明したフローチャートに記載された「2DdistanceField：２次元距離場」について説明する図。
【図１４】枝の長さと角度の制限について説明する図。
【図１５】３次元樹木形状生成装置によりモデリングした３次元樹木モデルを示す図。
【符号の説明】
【００２４】
１  ＰＣ、２  ２次元モデル作成部、３  ３次元モデル生成部、４  ３次元モデル編集部、５  枝編集部、６  マウス、７  ペンタブレット、８  キーボード９  モニタ、１００  ３次元樹木形状生成装置
【図１】
2005293259.tif 000003
【図２】
2005293259.tif 000004
【図３】
2005293259.tif 000005
【図４】
2005293259.tif 000006
【図５】
2005293259.tif 000007
【図６】
2005293259.tif 000008
【図７】
2005293259.tif 000009
【図８】
2005293259.tif 000010
【図９】
2005293259.tif 000011
【図１０】
2005293259.tif 000012
【図１１】
2005293259.tif 000013
【図１２】
2005293259.tif 000014
【図１４】
2005293259.tif 000015
【図１３】
2005293259.tif 000016
【図１５】
2005293259.tif 000017