３次元メッシュモデルの特徴稜線抽出装置、プログラム及び方法
【課題】３次元メッシュモデルからのソリッドモデルの自動生成を支援するための、広域的法線評価と改良Ｗａｔｅｒｓｈｅｄ法に基づく３次元メッシュモデルの特徴稜線抽出技術を提供する。
【解決手段】 ３次元メッシュモデルのデータを用い、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線と頂点の特徴量を算出し、算出した頂点特徴量の離散化および差分化を行うことにより、第１、第２の要求条件を満たす特徴稜線を抽出し、算出した特徴量に基づいて、頂点をグルーピング可能な改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出し、抽出した特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する。
【解決手段】 ３次元メッシュモデルのデータを用い、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線と頂点の特徴量を算出し、算出した頂点特徴量の離散化および差分化を行うことにより、第１、第２の要求条件を満たす特徴稜線を抽出し、算出した特徴量に基づいて、頂点をグルーピング可能な改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出し、抽出した特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソリッドモデルの自動生成を目的とした３次元メッシュモデルの特徴稜線抽出装置、プログラム及び方法に関する。
【背景技術】
【０００２】
近年、リバースエンジニアリングにおける３次元測定機の性能向上により、物理モデルからの高密度メッシュモデルの作成が可能となり、工業製品開発における意匠設計段階でこのようなメッシュモデルを用いる機会が多くなってきている。また、３次元（３Ｄ）データベース内のメッシュモデルが劇的に増加していることから、これらの検索から得られるメッシュモデルを再利用し、製品の意匠設計に用いることも可能となっている。
【０００３】
しかし、工業製品開発の詳細設計のためには、最終的に設計対象のソリッドモデルを生成することが必要となるが、現状ではこの３次元メッシュモデルからソリッドモデルを生成するために多くの時間を費やしている。そこで製品開発期間短縮のため、メッシュモデルからソリッドモデルを自動で生成する技術が望まれている。このような３次元メッシュモデルからのソリッドモデル生成に関する研究は、リバースエンジニアリングの分野で盛んに研究が行われているが、現状では複雑な形状のソリッドモデルを自動で生成することは困難である。
【０００４】
メッシュモデルからソリッドモデルを自動で生成するためのアプローチの１つに、まずメッシュモデルから特徴稜線を適切に抽出し、その特徴稜線を活かして曲面フィッティングを行う技術がある(P.Benko, R.R.Martin, and T.Varady. "Algorithms for reverse engineering boundary representation models." Computer-Aided Design 33(11), 839-851, 2001.―非特許文献１）。ここで述べる特徴稜線とは、機能的に１つの面分として認識することが望ましい連結された多角形（三角形メッシュの場合は三角形）集合からなる領域の境界線を意味する。この観点から、特徴稜線抽出に対する要求条件として以下の４つがある。
【０００５】
その第１の要求条件は、ノイズやメッシュ分割方法にできるだけ影響を受けずに特徴稜線が抽出できることである。第２の要求条件は、工業製品に多く含まれるフィレット面（面と面とをつなぐ丸い曲面）の境界線を特徴稜線として抽出できることである。第３の要求条件は、抽出される特徴稜線がループをなし、これに囲まれた領域を１つの面分として認識できることである。そして第４の要求条件は、ユーザの利用目的に応じた特徴稜線が選択的に抽出できることである。しかしながら既存の特徴稜線抽出技術では、上記４つの要求条件すべてを満たすものは知られていない。
【０００６】
メッシュモデルからの特徴稜線抽出する方法としては、大きく分けて２つの方法がある。１つは特徴稜線を直接抽出する方法であり、もう１つは領域分けの結果として得られる領域の境界線を特徴稜線として抽出する方法である。
【０００７】
前者の特徴稜線を直接抽出する方法は、『渡辺大地、千代倉弘明、「任意三角形メッシュからの特徴稜線抽出」、電子情報通信学会論文誌 D-IIJ83-D-II (5) 1344-1352, 2000.―非特許文献２』、『A.Meyer and P.Marin. "Segmentation of 3D triangulated data points using edges constructed with a C1 discontinuous surface fitting." Computer-Aided Design 36, 1327-1336, 2004.―非特許文献３』、『Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel. "Ridge-Valley Lines on Meshes via Implicit Surface Fitting." ACM Transactions on Graphics 23(3), 652-663, 2004.―非特許文献４』に提案されている。非特許文献２の方法は、三角形メッシュモデルの単純化の際に、形状特徴を表す稜線をできるだけ保存することを目的とし、まず各稜線に対して、稜線接続性、隣接２平面間角度、位相距離で定められる部分領域内の湾曲度の３つを考慮して稜線特徴量を算出し、この値がユーザの指定した閾値以上の稜線をグルーピングし特徴稜線として抽出するものである。しかしこの方法では、位相距離により定められた領域内の稜線群を評価し稜線特徴量を算出するため、抽出される特徴稜線がメッシュの分割方法の影響を受けやすいという問題点があった。さらに、閾値処理に基づき特徴稜線を抽出するため、特徴稜線がループを形成しないという問題点もあった。
【０００８】
非特許文献３の方法では、まずメッシュの２面角評価により処理の開始点を見つけ、次にその点から局所的な、不連続な形状をよく表現可能なａｂｓｏｉｄ曲面のフィッティングにより、本来の稜線の開始点を見つけ、そのａｂｓｏｉｄ曲面から得られる特徴稜線を生成することを繰り返し行い、最後に抽出された特徴稜線の端点を接続する。しかしこの方法では、複雑な形状が少ない数の三角形で構成される場合に特徴稜線がループをなさないことがある問題点があった。
【０００９】
非特許文献４では、まず入力メッシュモデルから生成した近似陰関数曲面上での曲率を計算し、次にこれをもとに特徴稜線を検出し、最後に検出した特徴稜線をもとのメッシュモデルに投影することで、特徴稜線を抽出する方法を提案している。この方法では、メッシュから直接計算することは困難である高次の微分値を、入力メッシュから近似し生成した陰関数曲面上で計算し、これをもとにメッシュ上の山線・谷線を抽出する。しかし、この方法では、抽出される特徴稜線がループをなさず、ループを形成するには複雑な後処理が必要となるという問題点があり、加えて、メッシュの向きにより異なる特徴稜線が抽出される、陰関数曲面上で高次の微分値を計算するため計算時間がかかるという問題点もあった。
【００１０】
後者の領域分けに基づく特徴稜線抽出方法として、『A.P.Mangan and R.T.Whitaker. "Partitioning 3D Surface Meshes Using Watershed Segmentation." IEEE Transactions on visualization and computer graphics 5(4), 308-321, 1999.―非特許文献５』、『Y. Sun, D. L. Page, J. K. Paik, A. Koschan, and M. A. Abidi. "Triangle mesh-based edge detection and its application to surface segmentation and adaptive surface smoothing." Proc. IEEE ICIP 2002, 825-828, 2002.―非特許文献６』、『Y. Sun. "Surface Modeling and Analysis Using Range Images, Smoothing, Registration, Integration and Segmentation." A Dissertation Presented for the Doctor of Philosophy Degree, The University of Tennessee, Knoxville, 2002.―非特許文献７』に、リバースエンジニアリングにより得られるノイズを多く含んだ三角形メッシュモデルの領域分けをする方法が提案されている。これらの方法では、まず各頂点の特徴量を算出し、次に算出した特徴量をもとにＷａｔｅｒｓｈｅｄ法を用いて領域分けを行うことで、各領域の境界線を特徴稜線として抽出することができる。しかしながら、Ｗａｔｅｒｓｈｅｄ法を用いると抽出される特徴稜線は頂点特徴量に大きく依存し、変化してしまう。そこで、特徴稜線抽出においてメッシュに含まれる測定ノイズやメッシュ分割方法の影響を受けにくくするためには、メッシュを局所的に評価するのではなく、メッシュを広域的に評価し、頂点特徴量を算出する必要がある。しかし、Ｗａｔｅｒｓｈｅｄ法では頂点集合からなる領域分けを行うため、隣接領域間にどの領域にも属さない三角形集合からなる隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないという問題点があった。
【００１１】
さらに、『S. Pulla, A. Razdan, and Gerald Farin. "Improved Curvature Estimation for Watershed Segmentation of 3-Dimensional Meshes." Arizona State University, Technical Report, 2001.―非特許文献８』では、特徴量を算出するために、まず入力メッシュの各頂点の近傍において近似ベジェ曲面を生成し、このベジェ曲面より各頂点の近似曲率を算出し、これを頂点特徴量とする方法が提案されている。この方法では、近似ペジェ曲面を生成する範囲を広域的に設定すれば、入力メッシュに含まれるノイズの影響は低減されるが、シャープな稜線上の頂点における特徴量に大きな誤差を含む問題点があった。また、算出される特徴量はその近似精度に依存し、近似精度を上げると計算時間がかかる問題点があった。
【００１２】
また、『A. Razdan and M. S. Bae. "A hybrid approach to feature segmentation of triangle meshes." Computer-Aided Design 35, 783-789, 2003.―非特許文献９』では、従来のＷａｔｅｒｓｈｅｄ法では適切に領域分けされなかった、ソリッドモデルやパラメトリック曲面モデルのテセレーションから得られる三角形メッシュモデルなどに多く見られる、１つの領域として認識したい面内に頂点を含まない面（例えば、長方形が２つの三角形から構成される場合など）を含むメッシュモデルを適切に領域分けできる、Ｗａｔｅｒｓｈｅｄ法をベースにした技術が提案されている。この非特許文献９の方法では、頂点特徴量算出には非特許文献８の方法を用いている。この方法では、すべての三角形がいずれかの領域に属する領域分けが行えるため、隣接領域間に隙間領域が生じず、その結果として抽出される特徴稜線は一致するといった利点がある。
【００１３】
『M. Vieira and K. Shimada. "Segmentation of Noisy Laser-Scanner Generated Meshes with Piecewise Polynomial Approximations." Proceedings of DETC '04, 2004.―非特許文献１０』では、入力メッシュの各頂点において近似双２次曲面を生成し、この近似曲面より各頂点の曲率を近似し、次にこの曲率に対してスムージングを適用することでノイズの影響をあまり受けないで特徴量を算出できる方法が提案されている。この方法ではさらに、上記の曲率を用いてシード領域を生成し、これを拡大していくことで頂点集合からなる領域分けを行う。しかし、この方法では頂点集合からなる領域を生成するため、隣接領域間にどの領域にも属さない三角形集合からなる隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないという問題点があり、さらに、頂点数の少ない領域が生成され、これらの領域の境界線は微小な特徴稜線として抽出されるため、後の応用に利用しにくい問題点があった。
【００１４】
特徴稜線抽出方法の別の提案として、『S. Katz and A. Tal. "Hierarchical mesh decomposition using fuzzy clustering and cuts." ACM Transactions on Graphics 22(3), 954-961, 2003.―非特許文献１１』には、過度な領域分けを回避でき、滑らかな境界線を抽出できる階層的な方法が提案されている。この方法では、メッシュの双対グラフに対するカットを最大流量アルゴリズムを用いて解くことにより領域分けを行う。しかし、この方法では工業製品の領域分けに必要な面分単位での領域分けが困難であり、処理時間がかかる問題点があった。
【００１５】
以上に述べたすべての従来技術には、共通の問題点として、いずれの方法もフィレット面の境界線を特徴稜線として適切に抽出できず、また、１通りの抽出パラメータ設定（例えば、特徴量を算出する際のメッシュの評価範囲を定めるパラメータ）では要求するすべての特徴稜線の抽出が困難である問題点があった。
【非特許文献１】P.Benko, R.R.Martin, and T.Varady. "Algorithms for reverse engineering boundary representation models." Computer-Aided Design 33(11), 839-851, 2001.
【非特許文献２】渡辺大地、千代倉弘明、「任意三角形メッシュからの特徴稜線抽出」、電子情報通信学会論文誌 D-IIJ83-D-II (5) 1344-1352, 2000.
【非特許文献３】A.Meyer and P.Marin. "Segmentation of 3D triangulated data points using edges constructed with a C1 discontinuous surface fitting." Computer-Aided Design 36, 1327-1336, 2004.
【非特許文献４】Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel. "Ridge-Valley Lines on Meshes via Implicit Surface Fitting." ACM Transactions on Graphics 23(3), 652-663, 2004.
【非特許文献５】A.P.Mangan and R.T.Whitaker. "Partitioning 3D Surface Meshes Using Watershed Segmentation." IEEE Transactions on visualization and computer graphics 5(4), 308-321, 1999.
【非特許文献６】Y. Sun, D. L. Page, J. K. Paik, A. Koschan, and M. A. Abidi. "Triangle mesh-based edge detection and its application to surface segmentation and adaptive surface smoothing." Proc. IEEE ICIP 2002, 825-828, 2002.
【非特許文献７】Y. Sun. "Surface Modeling and Analysis Using Range Images, Smoothing, Registration, Integration and Segmentation." A Dissertation Presented for the Doctor of Philosophy Degree, The University of Tennessee, Knoxville, 2002.
【非特許文献８】S. Pulla, A. Razdan, and Gerald Farin. "Improved Curvature Estimation for Watershed Segmentation of 3-Dimensional Meshes." Arizona State University, Technical Report, 2001.
【非特許文献９】A. Razdan and M. S. Bae. "A hybrid approach to feature segmentation of triangle meshes." Computer-Aided Design 35, 783-789, 2003.
【非特許文献１０】M. Vieira and K. Shimada. "Segmentation of Noisy Laser-Scanner Generated Meshes with Piecewise Polynomial Approximations." Proceedings of DETC '04, 2004.
【非特許文献１１】S. Katz and A. Tal. "Hierarchical mesh decomposition using fuzzy clustering and cuts." ACM Transactions on Graphics 22(3), 954-961, 2003.
【非特許文献１２】Andre Bleau and L. Joshua Leon. "Watershed-Based Segmentation and Region Merging." Computer Vision and Image Understanding 77(3), 317-370, 2000.
【非特許文献１３】J. B. T. M. Roerdink and A. Meijster. "Watershed Transform: Definitions, Algorithms and Parallelization Strategies." Fundamenta Informaticae 41, 87-228, IOS Press, 2001.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、上述のような従来技術の問題点に鑑みてなされたものであり、メッシュモデルからのソリッドモデルの自動生成を支援するための、上記の４つの要求条件をすべて満たす、広域的法線評価と改良Ｗａｔｅｒｓｈｅｄ法に基づく３次元メッシュモデルの特徴稜線抽出技術を提供することを目的とする。
【課題を解決するための手段】
【００１７】
請求項１の発明の３次元メッシュモデルの特徴稜線抽出装置は、諸データを保持する記憶手段と、前記記憶手段に保持されている３次元メッシュモデルを呼び出し、稜線特徴量と頂点特徴量を算出する特徴量算出手段と、前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する領域分け処理手段と、前記領域分け処理手段の抽出した特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する特徴稜線選択的抽出手段とを備えたものである。
【００１８】
請求項２の発明は、請求項１の３次元メッシュモデルの特徴稜線抽出装置において、前記特徴量算出手段は、前記記憶手段に保持されている３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、前記領域分け処理手段は、前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とするものである。
【００１９】
請求項３の発明の３次元メッシュモデルの特徴稜線抽出プログラムは、入力される若しくは記憶手段に保持されている３次元メッシュモデルのデータを呼び出す処理と、前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出する処理と、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する処理と、前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する処理とをコンピュータに実行させるものである。
【００２０】
請求項４の発明は、請求項３の３次元メッシュモデルの特徴稜線抽出プログラムにおいて、前記特徴量を算出する処理では、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、前記特徴稜線を抽出する処理では、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とするものである。
【００２１】
請求項５の発明は、請求項３又は４の３次元メッシュモデルの特徴稜線抽出プログラムにおいて、抽出パラメータと繰り返し回数を設定する処理を有し、前記処理各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返し実行することを特徴とするものである。
【００２２】
請求項６の発明の３次元メッシュモデルの特徴稜線抽出方法は、入力される若しくは記憶手段に保持されている３次元メッシュモデルを呼び出すステップと、前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出するステップと、算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出するステップと、前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力するステップとを有するものである。
【００２３】
請求項７の発明の３次元メッシュモデルの特徴稜線抽出方法は、前記特徴量を算出するステップでは、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、前記特徴稜線を抽出するステップでは、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とするものである。
【００２４】
請求項８の発明は、請求項６又は７の３次元メッシュモデルの特徴稜線抽出方法において、抽出パラメータと繰り返し回数を設定するステップを有し、前記ステップ各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返すことを特徴とするものである。
【発明の効果】
【００２５】
本発明によれば、メッシュに含まれる測定ノイズやメッシュ分割方法の影響をあまり受けずに特徴稜線抽出が可能である。また、特徴稜線で囲まれた領域を１つの面分として認識でき、従来の特徴稜線抽出技術では抽出しにくかったフィレット面の境界線を特徴稜線として抽出することができる。さらに、異なる抽出パラメータ設定より得られる特徴稜線群のうちのユーザが要求する稜線のみを選択的に合成し、これらを３次元ＣＡＤシステムで読み込む機能が実現できる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の実施の形態を図に基づいて詳説する。図１は、本発明の１つの実施の形態の３次元メッシュモデルの特徴稜線抽出装置の機能構成を示している。本実施の形態の装置はコンピュータシステムに下記諸演算処理機能を実行するソフトウェアをインストールすることによって実現されるものであるが、機能構成に分けて示すと、図２に示すように、頂点特徴量算出部１、領域分け処理部２、特徴稜線選択的抽出部３、そして諸データを格納する記憶装置４、抽出パラメータ設定部５、各部の演算処理機能を制御する演算処理制御部６、データ信号やその他の電気信号の入出力を行う入出力処理部７を備えている。そして通常コンピュータの周辺機器として最低限、入力手段としてキーボード８、マウスその他のポインティングデバイス９、また出力を表示するディスプレイ１０がこの装置に接続されている。
【００２７】
図２に示すように、本実施の形態の３次元メッシュモデルの特徴稜線抽出装置は、当該装置にて頂点特徴量算出処理ＳＱ１、領域分け処理ＳＱ２、特徴稜線選択的抽出処理ＳＱ３をそれぞれの該当処理部１〜３にて実行する。
【００２８】
頂点特徴量算出処理ＳＱ１では、メッシュ上において、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線や頂点の特徴量を算出する。さらに、頂点特徴量の離散化、および差分化を行うことによって特徴稜線を抽出する。領域分け処理ＳＱ２では、頂点特徴量算出部ＳＱ１で算出した特徴量に基づいて、頂点をグルーピング可能なＷａｔｅｒｓｈｅｄ法（T. Funkhouser, M. Kazhdan, P. Shilane, P. Min, W. Kiefer, A. Tal, S. Rusinkiewicz, and D. Dobkin. "Modeling by Example." ACM Transactions on Graphics 23(3), 609-612, 2004.）を改良した手法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する。これにより第３の要求条件を満たす特徴稜線が抽出できる。特徴稜線選択的抽出処理ＳＱ３は、領域分け処理ＳＱ２で抽出された特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させる。本実施の形態の３次元メッシュモデルの特徴稜線抽出装置では、これら３つの処理ＳＱ１〜ＳＱ３を、抽出パラメータ設定部５にて設定される異なる抽出パラメータ設定で数回繰り返し実行し、各パラメータ設定で抽出される特徴稜線群を対話的に集約する。
【００２９】
まず、頂点特徴量算出処理ＳＱ１について説明する。本実施の形態では、まず稜線の特徴量を算出し、この稜線特徴量をもとに頂点特徴量を算出する。稜線特徴量算出の最も単純な方法として、稜線を共有する２平面の２面角を計算する手法が考えられるが、この手法は２面角の値が大きなシャープな特徴稜線の抽出には有効だが、リバースエンジニアリングから得られるノイズを多く含んだメッシュモデルに対しては、局所的な形状に基づいた特徴量算出しか行っていないため、算出される特徴量がノイズの影響を受けやすく、隣接２平面の２面角の値が小さな特徴稜線の抽出は難しい。そこで本実施の形態では、稜線の近傍のユークリッド距離で定められる広域的な領域を評価し、特徴量を算出することで、この問題を解決する。図３は本実施の形態で実行する稜線特徴算出方法の説明図である。まず稜線ｅの中点を中心とする半径ｒの球Ｂを考える。次に、球Ｂに含まれる三角形の面法線ベクトルの和ｎ（バー）と稜線ｅとで定義した平面を用いて球Ｂを、２つの半球ＢＲ、ＢＬに分割する。次にＢＲ、ＢＬ内の各三角形面分の面積で重み付けした面法線ベクトルの和ｎＢＲ、ｎＢＬを数１式、数２式で計算する。
【数１】
【数２】
【００３０】
ここで、ｎｆは三角形面分ｆの単位面法線ベクトル、ＦＢＲ、ＦＢＬはＢＲ、ＢＬに含まれる三角形の集合、｜ｆ∩ＢＲ｜、｜ｆ∩ＢＬ｜はｆのＢＲ、ＢＬに含まれる部分の面積である。ただし、球や、球を分割した際に定義した平面と交差する三角形面分の球に含まれる部分の面積は、交差する部分を線分で置き換え、多角形で近似する。最後に面法線ベクトルｎＢＲ、ｎＢＬのなす角度を数３式で算出し、これを稜線ｅの特徴量θｅ（ｒ）とする。
【数３】
【００３１】
稜線特徴量θｅ（ｒ）の値が基本特徴稜線識別閾値τθより大きい稜線を基本特徴稜線、さらに基本特徴稜線の両端の頂点を基本特徴頂点と分類する。ここで、稜線の両端の頂点が基本特徴頂点であっても、必ずしもその稜線が基本特徴稜線とはならない。
【００３２】
次に、算出した稜線特徴量をもとに頂点特徴量を算出する。図４は頂点特徴算出のグラフであり、図５は各特徴量に基づく特徴稜線抽出結果の比較図である。それぞれ、（ａ）は連続特徴量、（ｂ）は離散特徴量、（ｃ）は差分特徴量を示している。まず頂点ｖに接続する稜線集合ｅ*（ｖ）内の稜線特徴量のうち、最も大きな稜線特徴量をｖの連続特徴量ｇｃｏｎ（ｖ）とする。
【数４】
【００３３】
数４式で得られる連続特徴量では、図４（ａ）のように本来１つの領域として認識したいフィレット面の頂点特徴量にばらつきが生じる。フィレットの開始位置にある頂点が小さい値を持ち、中央に近いほど大きな値を持ち、終了位置では開始位置と同じ小さい値を持つ。これをもとに後述する改良Ｗａｔｅｒｓｈｅｄ法を適用し領域分けを行うと、図５（ａ）のように、フィレット部が中央で２つに分割され、フィットの中央線が特徴稜線として抽出されてしまう。そこで図４（ｂ）のように、頂点特徴量離散化閾値τｖを用いてこの特徴量を離散化（２値化）したものをｇｄｉｓ（ｖ）とし、これによりフィレット面の頂点の特徴量を一定値にする。しかし、この離散特徴量では図５（ｂ）に示すように、Ｗａｔｅｒｓｈｅｄ法の性質上、抽出したいフィレット部はそれに滑らかに接続する片側の領域と同じ領域と認識され、フィレット面の片側の境界線しか抽出できない。そこで図４（ｃ）のように、頂点ｖの１近傍頂点との離散特徴量の差分を数５式で計算し、これを差分特徴量ｇｄｉｆ（ｖ）とする。これを用いることで図５（ｃ）に示すように、フィレット面の境界線が適切に抽出できる。
【数５】
【００３４】
ここでｖ＊はｖの隣接頂点集合である。本発明では、フィレット面の境界線抽出にのみ差分特徴量を、それ以外の特徴稜線抽出には連続特徴量を用いる。
【００３５】
次に、領域分け処理ＳＱ２について説明する。この演算処理では、改良したＷａｔｅｒｓｈｅｄ法を実行する。Ｗａｔｅｒｓｈｅｄ法は、画像の領域分け発明として提案された手法であり、画像処理の分野で今でも盛んに研究が行われている（非特許文献１２）。このＷａｔｅｒｓｈｅｄ法は、後に３次元メッシュモデルの領域分け手法に拡張された。非特許文献５では、水が高い所から低い所へ流れ落ちるように特徴量の大きい頂点から小さい頂点へとたどり、その過程でたどった頂点に共通の領域ラベルを割り当て、同じラベルを持つ頂点を１つの領域にグルーピングする手法が提案されている。
【００３６】
Ｗａｔｅｒｓｈｅｄ法は図６に示すように３つのステップからなる。図７は、Ｗａｔｅｒｓｈｅｄ法の概要を示す図であり、同図（ａ）がモデルの斜視図、同図（ｂ）が同図（ａ）の断面図、同図（ｃ）は同図（ａ）を展開し高さを特徴量とみなした曲線図、同図（ｄ）は頂点にラベルを割り当てた図、同図（ｅ）は同じ領域ラベルを持つ頂点をグルーピングした図、同図（ｆ）、（ｇ）は小さな領域を除去した図、同図（ｈ）は領域分けができなかった場合の図である。同図（ａ）では頂点特徴量を色分けしており、黒い頂点が大きい特徴量、白い頂点が小さい特徴量を持つ。
【００３７】
図６におけるステップＳＱ１１の局所最小値抽出処理は、図７（ｄ）に示すように、局所最小頂点抽出頂点特徴量が局所最小（その近傍の頂点がそれ自身より大きな特徴量を持つ）となる頂点集合を見つけ、それぞれの頂点に０から始まる固有の領域ラベルを割り当てる。
【００３８】
ステップＳＱ１２の降下処理は、図７（ｅ）に示すように、降下領域ラベルのない頂点をラベル付けされた領域（頂点集合）に到達するまで降下させ、その過程でたどった頂点すべてにその領域ラベルを割り当て、同じ領域ラベルを持つ頂点を１つの領域にグルーピングする。
【００３９】
ステップＳＱ１３の領域統合処理は次の通りである。ステップＳＱ１２で頂点集合からなる領域分けを行った際に、少ない数の頂点集合からなる小さな領域ができやすい。これらの領域の境界線として後に抽出される特徴稜線は、その利用の観点から見て好ましくなく、除去することが望ましい。そこでまず、領域内の最も低い連続特徴量を持つ頂点と、その領域の境界とその領域に隣接する領域の境界の頂点のうちの最も低い連続特徴量を持つ頂点ｖｂｏｕとの連続特徴量の差分を計算する。この差分をＷａｔｅｒｓｈｅｄ深さと呼ぶ。領域内の頂点数が領域内最小頂点数閾値τｎより少なく、かつ、Ｗａｔｅｒｓｈｅｄ深さが領域統合閾値τｄより小さい領域を、ｖｂｏｕに隣接する領域と統合する。この処理を上の条件を満たす領域がなくなるまで繰り返し、図７（ｆ）、図７（ｇ）のように小さな領域を除去する。
【００４０】
このＷａｔｅｒｓｈｅｄ法は頂点のみに領域ラベルを割り当て頂点集合からなる領域分けを行うため、３つの頂点の領域ラベルが一致せずどの領域にも属さない三角形集合からなる隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないといった問題点がある。また、図７（ｈ）に示すように認識すべき面分の内部に頂点がない（例えば、長方形が２つの直角三角形から構成される）場合に適切な領域分けができないといった問題点もある。
【００４１】
このような問題点を解決するため、非特許文献９に特徴稜線抽出精度向上のための改良を加えた改良Ｗａｔｅｒｓｈｅｄ法が提案されている。この手法では、Ｗａｔｅｒｓｈｅｄ法と三角形への領域ラベルの割り当てに基づき、三角形集合からなる領域分けが可能である。改良Ｗａｔｅｒｓｈｅｄ法は図８に示すように５つの処理ステップからなる。つまり、頂点追加処理のステップＳＱ２１、頂点特徴量算出のステップＳＱ２２、Ｗａｔｅｒｓｈｅｄ法による処理ステップＳＱ２３、頂点削除処理のステップＳＱ２４、そして面分への領域ラベル割り当て処理をするステップＳＱ２５である。
【００４２】
図９（ａ）は認識すべき面分の内部に頂点を含まないメッシュモデルの斜視図である。図９（ｂ）〜図９（ｇ）は、図９（ａ）の断面図を展開し、高さを特徴量とみなした曲線図である。この図では、線分はメッシュの三角形を表す。また、図１０は頂点追加の規則を説明する図である。
【００４３】
図８におけるステップＳＱ２１は、１つの領域として認識すべき面分集合内に頂点がない部分を適切に認識するため、メッシュ上の基本特徴稜線、図９（ｂ）の基本特徴頂点の分布状況に基づき、図９（ｃ）のように図１０に示す頂点追加規則に従って各辺の中点に頂点を追加する。
【００４４】
ステップＳＱ２２は、図９（ｄ）に示すように、追加した頂点のうち、基本特徴稜線上にある頂点には全頂点のうち最大特徴量を、三角形の面上にある頂点には全頂点のうち最小特徴量を、それ以外の頂点にはその頂点が追加された稜線の特徴量を定義する。
【００４５】
ステップＳＱ２３は、図９（ｅ）に示すように、頂点を追加したメッシュモデルにＷａｔｅｒｓｈｅｄ法を適用し各頂点に領域ラベルを割り当て、頂点集合からなる領域分けを行う。
【００４６】
ステップＳＱ２４は、図９（ｆ）に示すように、基本特徴頂点にそれら自身の領域ラベルとともに１近傍頂点の領域ラベルも付加した後、ステップＳＱ２１で追加した頂点をメッシュから削除する。これにより、基本特徴頂点は複数の領域ラベルを持つことになる。
【００４７】
ステップＳＱ２５は、図９（ｇ）に示すように、図１１の表に示す頂点ラベルの割り当て状況に従って各三角形に対して１つずつ領域ラベルを割り当てる。特にｃａｓｅ２〜ｃａｓｅ５は、ソリッドモデルのテセレーションなどにより得られる、１つの面分として認識したい領域内部に頂点を含まないために適切に領域分けできなかったメッシュモデルを領域分けする際に有効である。一方、ｃａｓｅ６は、リバースエンジニアリングから得られた高密度メッシュモデルにＷａｔｅｒｓｈｅｄ法を適用した場合に生じる隙間領域の三角形に適切に領域ラベルを割り当てる際に有効である。これによりすべての三角形に一つずつ領域ラベルが割り当てられ、同じ領域ラベルを持つ三角形群を１つの面分としてグルーピングする。
【００４８】
以上の５つのステップＳＱ２１〜ＳＱ２５により、メッシュモデルに対し連結三角形集合からなる領域分けを行い、最後に各領域の境界線を特徴稜線として抽出する。図１２は従来のＷａｔｅｒｓｈｅｄ法と、改良Ｗａｔｅｒｓｈｅｄ法を用いて領域分けを行った結果の比較図である。図１２（ａ）、（ｂ）は従来のＷａｔｅｒｓｈｅｄ法を用いた場合であり、同図（ｃ）、（ｄ）は改良Ｗａｔｅｒｓｈｅｄ法を用いた場合である。従来のＷａｔｅｒｓｈｅｄ法では、図１２（ａ）のように隣接領域間に隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないといった問題点、さらに、図１２（ｂ）のように１つの面分として認識したい領域の内部に頂点がない場合に適切な領域分けができないといった問題点を持つことが分かる。これに対し、改良Ｗａｔｅｒｓｈｅｄ法を用いることで、これらの問題点が解決され、図１２（ｃ）のように特徴稜線が共有され、また図１２（ｄ）のように適切な領域分けができていることが確認できる。
【００４９】
次に、本実施の形態の装置にて実施する３次元メッシュモデルの特徴稜線抽出方法で用いる５つの抽出パラメータが、特徴稜線抽出に与える効果について説明する。この抽出パラメータは抽出パラメータ設定部５により行う。球の半径ｒは、稜線特徴量を算出する際の評価範囲を定めるために用いる。この値を小さくすると評価範囲が局所的になり、シャープな特徴稜線が抽出しやすくなり、大きくすると評価範囲が広域的になり、形状がなだらかに変化する部分にある特徴稜線が抽出しやすくなる。
【００５０】
頂点特徴量離散化閾値τｖは、フィレット面の境界線の抽出位置を調整する際に用いる。この値は、フィレット面の境界線上にある頂点が持つ特徴量に一致するよう、適切に設定する必要がある。この適切値より小さく設定すると、抽出したいフィレット面より広いフィレット面の境界線が抽出されてしまい、大きくすると抽出したいフィレット面より狭いフィレット面の境界線が抽出される。
【００５１】
基本特徴稜線識別閾値τθは、主にクリースエッジの抽出の際に用いる。大きくする設定すると隣接面との２面角が大きい面の境界線のみが抽出でき、この値を小さく設定すると隣接面との２面角が大きい面の境界線のみならず、小さい面の境界線もが抽出できる。
【００５２】
領域内最小頂点数閾値τｎこの値を小さく設定すると、少ない数の頂点集合からなる領域分けが行われ、その境界線が抽出でき、大きく設定すると、多い数の頂点集合からなる領域分けが行われ、その境界線のみ抽出できる。
【００５３】
領域統合閾値τｄは、この値を小さく設定すると、領域内の頂点特徴量の差が少ない領域分けが行われ、その境界線が抽出でき、大きくすると、領域内の頂点特徴量の差が大きい領域分けが行われ、その境界線のみ抽出できる。
【００５４】
上述した処理ＳＱ１の基本特徴稜線と基本特徴頂点に分類する手法を１通りのパラメータ設定で一度実行しただけでは、要求する特徴稜線のすべてを抽出することは困難である。そこで、以上の手法を異なる抽出パラメータ設定で繰り返し実行し、各抽出パラメータ設定で抽出される特徴稜線のうちのユーザの要求する稜線をディスプレイ上で対話的に選択し、集約することでこの問題を解決する。
【００５５】
本実施の形態の装置では、効率の良いユーザの特徴稜線抽出のために２つの特徴稜線選択手法を実装している。第１は、領域境界線ループの抽出である。これは、図１３（ａ）に示すように、領域内の面分の選択によって、領域境界のループをなす特徴稜線群を全て抽出する。第２は、区分特徴稜線の抽出である。これは、特徴稜線上のメッシュの稜線の選択によって、図１３（ｂ）に示すように３つ以上の特徴稜線が交わる頂点で境界付けられた区分的な特徴稜線を抽出する。これらを使い分けることで、あらゆる特徴稜線が選択的に集約でき、ユーザの要求する特徴稜線のみを抽出できる。
【００５６】
本実施の形態では、メッシュモデルからのソリッドモデルの自動生成を目的とした、広域的法線評価と改良Ｗａｔｅｒｓｈｅｄ法に基づく特徴稜線抽出が行える。
【実施例】
【００５７】
実験により、本発明を用いることで、メッシュに含まれるノイズやメッシュ分割方法の影響を受けにくく特徴稜線が抽出できること、またフィレット面の境界線を特徴稜線として抽出できること、抽出された特徴稜線がループをなし、それに囲まれる領域を１つの面分として認識できること、利用目的に応じた特徴稜線が選択的に抽出できることを確認した。また、抽出した特徴稜線の３次元ＣＡＤシステムへの読み込みも実現した。
【００５８】
図１４に、硬質ウレタンフォームで作られたＩＴ機器筐体モックアップ（ａ）を非接触測定器（Ｃｏｍｅｔ４００：商品名）で計測して得られた点群（約１４０万点）から三角形メッシュを生成した高密度メッシュモデル（ｂ）に対する特徴稜線抽出結果を示している。図１４（ｃ）、（ｅ）はそれぞれ異なる抽出パラメータで領域分けを行った結果である。同図（ｄ）、（ｆ）はそれぞれ、同図（ｃ）、（ｅ）の領域の境界線を特徴稜線として抽出した結果である。このような測定ノイズを多く含むメッシュモデルからも、抽出パラメータを適切に設定することで特徴稜線が抽出できることが確認できた。処理時間は、Ｘｅｏｎ２．４ＧＨｚ、メモリ２ＧＢのＰＣで１通りの抽出パラメータ設定での自動抽出処理に約６分（頂点特徴量算出に約５分、領域分けに基づく特徴稜線抽出に約１分）であった。
【００５９】
図１５に、ソリッドモデルを異なる分割方法で分割し得られたメッシュモデルに対する特徴稜線抽出結果を示している。図１５（ａ）の上段はＦＥＭメッシャにより分割して得られた高密度メッシュ、同図（ｂ）の上段はＦＥＭメッシャにより分割して得られた低解像度メッシュ、同図（ｃ）の上段はＳＴＬデータへの変換により得られたメッシュである。また、同図（ａ）〜（ｃ）の下段それぞれは、これらのメッシュモデルに対して本発明の特徴稜線抽出方法を何度か繰り返し実行し、特徴稜線を集約した結果である。図１５に示すように、分割方法の異なるメッシュモデルからも、ほぼ等しい特徴稜線が抽出できることが確認できた。図１５（ａ）、（ｂ）に関しては、メッシュの稜線はソリッドモデルを生成した際に定義した稜線上にある保障はない。それゆえ本来のソリッドモデル上の稜線に最も近いと思われる稜線を特徴稜線として抽出した結果、若干の誤差が見られた。
【００６０】
球の半径ｒの値は厳密に設定する必要はなく、例えば、物理モデルを測定して得られるノイズを多く含んだメッシュモデルに対しては、入力メッシュのＢｏｕｎｄｉｎｇＢｏｘの対角線の５０分の１〜１００分の１程度に設定すると良い結果が得られやすい。また、隣接２平面の２面角が大きいクリースエッジを多く含んだメッシュに対しては、ｒを小さな値に設定すると良い結果を得られやすい。また、図１４のように、頂点特徴量離散化閾値τｖを変更することで、径の小さなフィレット面、大きなフィレット面の境界線がそれぞれ抽出できることが確認できた。
【００６１】
図１６に、ユーザにより選択された特徴稜線の集約結果を示す。入力は、ソリッドモデルをＦＥＭメッシャにより分割して得られたひずみの小さい三角形からなるメッシュモデル（三角形数約６５、０００）である。図中の細い線がある抽出パラメータ設定で抽出されたすべての特徴稜線、太い線がユーザにより選択された特徴稜線である。図１６（ａ）〜（ｃ）の３通りの抽出パラメータ設定での特徴稜線の集約結果が図１６（ｄ）である。これより、異なる抽出パラメータ設定で抽出される特徴稜線が集約できることが分かる。処理時間は１通りの抽出パラメータ設定での自動抽出処理で、約４秒〜２６秒であった。
【００６２】
図１４〜図１６により、抽出された特徴稜線がループをなすこと、また、フィレット面の境界線が特徴稜線として抽出できていることが確認できた。
【００６３】
さらに、図１６のようにして得られた特徴稜線を３次元ＣＡＤシステム（ＳｏｌｉｄＷｏｒｋｓ：商品名）内に読み込んだ結果を図１７に示す。これより、集約された特徴稜線が３次元ＣＡＤシステムに正しく読み込まれていることが確認できた。
【図面の簡単な説明】
【００６４】
【図１】本発明の１つの実施の形態の３次元メッシュモデルの特徴稜線抽出装置のブロック図。
【図２】本発明の１つの実施の形態の３次元メッシュモデルの特徴稜線抽出装置が実行する３次元メッシュモデルの特徴稜線抽出プログラム及び方法のフローチャート。
【図３】上記実施の形態で実行される稜線特徴算出処理の説明図。
【図４】上記実施の形態で実行される頂点特徴算出処理のグラフ図。
【図５】上記実施の形態で抽出された特徴稜線の比較図。
【図６】Ｗａｔｅｒｓｈｅｄ法のシーケンス図。
【図７】Ｗａｔｅｒｓｈｅｄ法の説明図。
【図８】上記実施の形態で実行する改良Ｗａｔｅｒｓｈｅｄ法のシーケンス図。
【図９】上記実施の形態の改良Ｗａｔｅｒｓｈｅｄ法の説明図。
【図１０】上記実施の形態で採用した頂点追加規則の説明図。
【図１１】上記実施の形態で採用した頂点追加規則の表。
【図１２】従来のＷａｔｅｒｓｈｅｄ法と本実施の形態で実行する改良Ｗａｔｅｒｓｈｅｄ法とを用いて領域分けを行った結果の比較図。
【図１３】上記実施の形態で実行する特徴稜線の選択的抽出処理の説明図。
【図１４】本発明の実施例の特徴稜線抽出結果を示す図。
【図１５】本発明の実施例の物理モデルを異なる分割方法で分割し得られたメッシュモデルに対する特徴稜線抽出結果を示す図。
【図１６】本発明の実施例において複数の選択された特徴稜線の集約結果を示す図。
【図１７】図１６により得られた特徴稜線を３次元ＣＡＤシステム内に読み込んだ結果を示す図。
【符号の説明】
【００６５】
１ 頂点特徴量算出部
２領域分け処理部
３ 特徴稜線選択的抽出部
４記憶装置
５ 抽出パラメータ設定部
６ 演算処理制御部
７ 入出力処理部
８ キーボード
９ ポインティングデバイス
１０ ディスプレイ
【技術分野】
【０００１】
本発明は、ソリッドモデルの自動生成を目的とした３次元メッシュモデルの特徴稜線抽出装置、プログラム及び方法に関する。
【背景技術】
【０００２】
近年、リバースエンジニアリングにおける３次元測定機の性能向上により、物理モデルからの高密度メッシュモデルの作成が可能となり、工業製品開発における意匠設計段階でこのようなメッシュモデルを用いる機会が多くなってきている。また、３次元（３Ｄ）データベース内のメッシュモデルが劇的に増加していることから、これらの検索から得られるメッシュモデルを再利用し、製品の意匠設計に用いることも可能となっている。
【０００３】
しかし、工業製品開発の詳細設計のためには、最終的に設計対象のソリッドモデルを生成することが必要となるが、現状ではこの３次元メッシュモデルからソリッドモデルを生成するために多くの時間を費やしている。そこで製品開発期間短縮のため、メッシュモデルからソリッドモデルを自動で生成する技術が望まれている。このような３次元メッシュモデルからのソリッドモデル生成に関する研究は、リバースエンジニアリングの分野で盛んに研究が行われているが、現状では複雑な形状のソリッドモデルを自動で生成することは困難である。
【０００４】
メッシュモデルからソリッドモデルを自動で生成するためのアプローチの１つに、まずメッシュモデルから特徴稜線を適切に抽出し、その特徴稜線を活かして曲面フィッティングを行う技術がある(P.Benko, R.R.Martin, and T.Varady. "Algorithms for reverse engineering boundary representation models." Computer-Aided Design 33(11), 839-851, 2001.―非特許文献１）。ここで述べる特徴稜線とは、機能的に１つの面分として認識することが望ましい連結された多角形（三角形メッシュの場合は三角形）集合からなる領域の境界線を意味する。この観点から、特徴稜線抽出に対する要求条件として以下の４つがある。
【０００５】
その第１の要求条件は、ノイズやメッシュ分割方法にできるだけ影響を受けずに特徴稜線が抽出できることである。第２の要求条件は、工業製品に多く含まれるフィレット面（面と面とをつなぐ丸い曲面）の境界線を特徴稜線として抽出できることである。第３の要求条件は、抽出される特徴稜線がループをなし、これに囲まれた領域を１つの面分として認識できることである。そして第４の要求条件は、ユーザの利用目的に応じた特徴稜線が選択的に抽出できることである。しかしながら既存の特徴稜線抽出技術では、上記４つの要求条件すべてを満たすものは知られていない。
【０００６】
メッシュモデルからの特徴稜線抽出する方法としては、大きく分けて２つの方法がある。１つは特徴稜線を直接抽出する方法であり、もう１つは領域分けの結果として得られる領域の境界線を特徴稜線として抽出する方法である。
【０００７】
前者の特徴稜線を直接抽出する方法は、『渡辺大地、千代倉弘明、「任意三角形メッシュからの特徴稜線抽出」、電子情報通信学会論文誌 D-IIJ83-D-II (5) 1344-1352, 2000.―非特許文献２』、『A.Meyer and P.Marin. "Segmentation of 3D triangulated data points using edges constructed with a C1 discontinuous surface fitting." Computer-Aided Design 36, 1327-1336, 2004.―非特許文献３』、『Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel. "Ridge-Valley Lines on Meshes via Implicit Surface Fitting." ACM Transactions on Graphics 23(3), 652-663, 2004.―非特許文献４』に提案されている。非特許文献２の方法は、三角形メッシュモデルの単純化の際に、形状特徴を表す稜線をできるだけ保存することを目的とし、まず各稜線に対して、稜線接続性、隣接２平面間角度、位相距離で定められる部分領域内の湾曲度の３つを考慮して稜線特徴量を算出し、この値がユーザの指定した閾値以上の稜線をグルーピングし特徴稜線として抽出するものである。しかしこの方法では、位相距離により定められた領域内の稜線群を評価し稜線特徴量を算出するため、抽出される特徴稜線がメッシュの分割方法の影響を受けやすいという問題点があった。さらに、閾値処理に基づき特徴稜線を抽出するため、特徴稜線がループを形成しないという問題点もあった。
【０００８】
非特許文献３の方法では、まずメッシュの２面角評価により処理の開始点を見つけ、次にその点から局所的な、不連続な形状をよく表現可能なａｂｓｏｉｄ曲面のフィッティングにより、本来の稜線の開始点を見つけ、そのａｂｓｏｉｄ曲面から得られる特徴稜線を生成することを繰り返し行い、最後に抽出された特徴稜線の端点を接続する。しかしこの方法では、複雑な形状が少ない数の三角形で構成される場合に特徴稜線がループをなさないことがある問題点があった。
【０００９】
非特許文献４では、まず入力メッシュモデルから生成した近似陰関数曲面上での曲率を計算し、次にこれをもとに特徴稜線を検出し、最後に検出した特徴稜線をもとのメッシュモデルに投影することで、特徴稜線を抽出する方法を提案している。この方法では、メッシュから直接計算することは困難である高次の微分値を、入力メッシュから近似し生成した陰関数曲面上で計算し、これをもとにメッシュ上の山線・谷線を抽出する。しかし、この方法では、抽出される特徴稜線がループをなさず、ループを形成するには複雑な後処理が必要となるという問題点があり、加えて、メッシュの向きにより異なる特徴稜線が抽出される、陰関数曲面上で高次の微分値を計算するため計算時間がかかるという問題点もあった。
【００１０】
後者の領域分けに基づく特徴稜線抽出方法として、『A.P.Mangan and R.T.Whitaker. "Partitioning 3D Surface Meshes Using Watershed Segmentation." IEEE Transactions on visualization and computer graphics 5(4), 308-321, 1999.―非特許文献５』、『Y. Sun, D. L. Page, J. K. Paik, A. Koschan, and M. A. Abidi. "Triangle mesh-based edge detection and its application to surface segmentation and adaptive surface smoothing." Proc. IEEE ICIP 2002, 825-828, 2002.―非特許文献６』、『Y. Sun. "Surface Modeling and Analysis Using Range Images, Smoothing, Registration, Integration and Segmentation." A Dissertation Presented for the Doctor of Philosophy Degree, The University of Tennessee, Knoxville, 2002.―非特許文献７』に、リバースエンジニアリングにより得られるノイズを多く含んだ三角形メッシュモデルの領域分けをする方法が提案されている。これらの方法では、まず各頂点の特徴量を算出し、次に算出した特徴量をもとにＷａｔｅｒｓｈｅｄ法を用いて領域分けを行うことで、各領域の境界線を特徴稜線として抽出することができる。しかしながら、Ｗａｔｅｒｓｈｅｄ法を用いると抽出される特徴稜線は頂点特徴量に大きく依存し、変化してしまう。そこで、特徴稜線抽出においてメッシュに含まれる測定ノイズやメッシュ分割方法の影響を受けにくくするためには、メッシュを局所的に評価するのではなく、メッシュを広域的に評価し、頂点特徴量を算出する必要がある。しかし、Ｗａｔｅｒｓｈｅｄ法では頂点集合からなる領域分けを行うため、隣接領域間にどの領域にも属さない三角形集合からなる隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないという問題点があった。
【００１１】
さらに、『S. Pulla, A. Razdan, and Gerald Farin. "Improved Curvature Estimation for Watershed Segmentation of 3-Dimensional Meshes." Arizona State University, Technical Report, 2001.―非特許文献８』では、特徴量を算出するために、まず入力メッシュの各頂点の近傍において近似ベジェ曲面を生成し、このベジェ曲面より各頂点の近似曲率を算出し、これを頂点特徴量とする方法が提案されている。この方法では、近似ペジェ曲面を生成する範囲を広域的に設定すれば、入力メッシュに含まれるノイズの影響は低減されるが、シャープな稜線上の頂点における特徴量に大きな誤差を含む問題点があった。また、算出される特徴量はその近似精度に依存し、近似精度を上げると計算時間がかかる問題点があった。
【００１２】
また、『A. Razdan and M. S. Bae. "A hybrid approach to feature segmentation of triangle meshes." Computer-Aided Design 35, 783-789, 2003.―非特許文献９』では、従来のＷａｔｅｒｓｈｅｄ法では適切に領域分けされなかった、ソリッドモデルやパラメトリック曲面モデルのテセレーションから得られる三角形メッシュモデルなどに多く見られる、１つの領域として認識したい面内に頂点を含まない面（例えば、長方形が２つの三角形から構成される場合など）を含むメッシュモデルを適切に領域分けできる、Ｗａｔｅｒｓｈｅｄ法をベースにした技術が提案されている。この非特許文献９の方法では、頂点特徴量算出には非特許文献８の方法を用いている。この方法では、すべての三角形がいずれかの領域に属する領域分けが行えるため、隣接領域間に隙間領域が生じず、その結果として抽出される特徴稜線は一致するといった利点がある。
【００１３】
『M. Vieira and K. Shimada. "Segmentation of Noisy Laser-Scanner Generated Meshes with Piecewise Polynomial Approximations." Proceedings of DETC '04, 2004.―非特許文献１０』では、入力メッシュの各頂点において近似双２次曲面を生成し、この近似曲面より各頂点の曲率を近似し、次にこの曲率に対してスムージングを適用することでノイズの影響をあまり受けないで特徴量を算出できる方法が提案されている。この方法ではさらに、上記の曲率を用いてシード領域を生成し、これを拡大していくことで頂点集合からなる領域分けを行う。しかし、この方法では頂点集合からなる領域を生成するため、隣接領域間にどの領域にも属さない三角形集合からなる隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないという問題点があり、さらに、頂点数の少ない領域が生成され、これらの領域の境界線は微小な特徴稜線として抽出されるため、後の応用に利用しにくい問題点があった。
【００１４】
特徴稜線抽出方法の別の提案として、『S. Katz and A. Tal. "Hierarchical mesh decomposition using fuzzy clustering and cuts." ACM Transactions on Graphics 22(3), 954-961, 2003.―非特許文献１１』には、過度な領域分けを回避でき、滑らかな境界線を抽出できる階層的な方法が提案されている。この方法では、メッシュの双対グラフに対するカットを最大流量アルゴリズムを用いて解くことにより領域分けを行う。しかし、この方法では工業製品の領域分けに必要な面分単位での領域分けが困難であり、処理時間がかかる問題点があった。
【００１５】
以上に述べたすべての従来技術には、共通の問題点として、いずれの方法もフィレット面の境界線を特徴稜線として適切に抽出できず、また、１通りの抽出パラメータ設定（例えば、特徴量を算出する際のメッシュの評価範囲を定めるパラメータ）では要求するすべての特徴稜線の抽出が困難である問題点があった。
【非特許文献１】P.Benko, R.R.Martin, and T.Varady. "Algorithms for reverse engineering boundary representation models." Computer-Aided Design 33(11), 839-851, 2001.
【非特許文献２】渡辺大地、千代倉弘明、「任意三角形メッシュからの特徴稜線抽出」、電子情報通信学会論文誌 D-IIJ83-D-II (5) 1344-1352, 2000.
【非特許文献３】A.Meyer and P.Marin. "Segmentation of 3D triangulated data points using edges constructed with a C1 discontinuous surface fitting." Computer-Aided Design 36, 1327-1336, 2004.
【非特許文献４】Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel. "Ridge-Valley Lines on Meshes via Implicit Surface Fitting." ACM Transactions on Graphics 23(3), 652-663, 2004.
【非特許文献５】A.P.Mangan and R.T.Whitaker. "Partitioning 3D Surface Meshes Using Watershed Segmentation." IEEE Transactions on visualization and computer graphics 5(4), 308-321, 1999.
【非特許文献６】Y. Sun, D. L. Page, J. K. Paik, A. Koschan, and M. A. Abidi. "Triangle mesh-based edge detection and its application to surface segmentation and adaptive surface smoothing." Proc. IEEE ICIP 2002, 825-828, 2002.
【非特許文献７】Y. Sun. "Surface Modeling and Analysis Using Range Images, Smoothing, Registration, Integration and Segmentation." A Dissertation Presented for the Doctor of Philosophy Degree, The University of Tennessee, Knoxville, 2002.
【非特許文献８】S. Pulla, A. Razdan, and Gerald Farin. "Improved Curvature Estimation for Watershed Segmentation of 3-Dimensional Meshes." Arizona State University, Technical Report, 2001.
【非特許文献９】A. Razdan and M. S. Bae. "A hybrid approach to feature segmentation of triangle meshes." Computer-Aided Design 35, 783-789, 2003.
【非特許文献１０】M. Vieira and K. Shimada. "Segmentation of Noisy Laser-Scanner Generated Meshes with Piecewise Polynomial Approximations." Proceedings of DETC '04, 2004.
【非特許文献１１】S. Katz and A. Tal. "Hierarchical mesh decomposition using fuzzy clustering and cuts." ACM Transactions on Graphics 22(3), 954-961, 2003.
【非特許文献１２】Andre Bleau and L. Joshua Leon. "Watershed-Based Segmentation and Region Merging." Computer Vision and Image Understanding 77(3), 317-370, 2000.
【非特許文献１３】J. B. T. M. Roerdink and A. Meijster. "Watershed Transform: Definitions, Algorithms and Parallelization Strategies." Fundamenta Informaticae 41, 87-228, IOS Press, 2001.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、上述のような従来技術の問題点に鑑みてなされたものであり、メッシュモデルからのソリッドモデルの自動生成を支援するための、上記の４つの要求条件をすべて満たす、広域的法線評価と改良Ｗａｔｅｒｓｈｅｄ法に基づく３次元メッシュモデルの特徴稜線抽出技術を提供することを目的とする。
【課題を解決するための手段】
【００１７】
請求項１の発明の３次元メッシュモデルの特徴稜線抽出装置は、諸データを保持する記憶手段と、前記記憶手段に保持されている３次元メッシュモデルを呼び出し、稜線特徴量と頂点特徴量を算出する特徴量算出手段と、前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する領域分け処理手段と、前記領域分け処理手段の抽出した特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する特徴稜線選択的抽出手段とを備えたものである。
【００１８】
請求項２の発明は、請求項１の３次元メッシュモデルの特徴稜線抽出装置において、前記特徴量算出手段は、前記記憶手段に保持されている３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、前記領域分け処理手段は、前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とするものである。
【００１９】
請求項３の発明の３次元メッシュモデルの特徴稜線抽出プログラムは、入力される若しくは記憶手段に保持されている３次元メッシュモデルのデータを呼び出す処理と、前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出する処理と、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する処理と、前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する処理とをコンピュータに実行させるものである。
【００２０】
請求項４の発明は、請求項３の３次元メッシュモデルの特徴稜線抽出プログラムにおいて、前記特徴量を算出する処理では、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、前記特徴稜線を抽出する処理では、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とするものである。
【００２１】
請求項５の発明は、請求項３又は４の３次元メッシュモデルの特徴稜線抽出プログラムにおいて、抽出パラメータと繰り返し回数を設定する処理を有し、前記処理各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返し実行することを特徴とするものである。
【００２２】
請求項６の発明の３次元メッシュモデルの特徴稜線抽出方法は、入力される若しくは記憶手段に保持されている３次元メッシュモデルを呼び出すステップと、前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出するステップと、算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出するステップと、前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力するステップとを有するものである。
【００２３】
請求項７の発明の３次元メッシュモデルの特徴稜線抽出方法は、前記特徴量を算出するステップでは、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、前記特徴稜線を抽出するステップでは、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とするものである。
【００２４】
請求項８の発明は、請求項６又は７の３次元メッシュモデルの特徴稜線抽出方法において、抽出パラメータと繰り返し回数を設定するステップを有し、前記ステップ各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返すことを特徴とするものである。
【発明の効果】
【００２５】
本発明によれば、メッシュに含まれる測定ノイズやメッシュ分割方法の影響をあまり受けずに特徴稜線抽出が可能である。また、特徴稜線で囲まれた領域を１つの面分として認識でき、従来の特徴稜線抽出技術では抽出しにくかったフィレット面の境界線を特徴稜線として抽出することができる。さらに、異なる抽出パラメータ設定より得られる特徴稜線群のうちのユーザが要求する稜線のみを選択的に合成し、これらを３次元ＣＡＤシステムで読み込む機能が実現できる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の実施の形態を図に基づいて詳説する。図１は、本発明の１つの実施の形態の３次元メッシュモデルの特徴稜線抽出装置の機能構成を示している。本実施の形態の装置はコンピュータシステムに下記諸演算処理機能を実行するソフトウェアをインストールすることによって実現されるものであるが、機能構成に分けて示すと、図２に示すように、頂点特徴量算出部１、領域分け処理部２、特徴稜線選択的抽出部３、そして諸データを格納する記憶装置４、抽出パラメータ設定部５、各部の演算処理機能を制御する演算処理制御部６、データ信号やその他の電気信号の入出力を行う入出力処理部７を備えている。そして通常コンピュータの周辺機器として最低限、入力手段としてキーボード８、マウスその他のポインティングデバイス９、また出力を表示するディスプレイ１０がこの装置に接続されている。
【００２７】
図２に示すように、本実施の形態の３次元メッシュモデルの特徴稜線抽出装置は、当該装置にて頂点特徴量算出処理ＳＱ１、領域分け処理ＳＱ２、特徴稜線選択的抽出処理ＳＱ３をそれぞれの該当処理部１〜３にて実行する。
【００２８】
頂点特徴量算出処理ＳＱ１では、メッシュ上において、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線や頂点の特徴量を算出する。さらに、頂点特徴量の離散化、および差分化を行うことによって特徴稜線を抽出する。領域分け処理ＳＱ２では、頂点特徴量算出部ＳＱ１で算出した特徴量に基づいて、頂点をグルーピング可能なＷａｔｅｒｓｈｅｄ法（T. Funkhouser, M. Kazhdan, P. Shilane, P. Min, W. Kiefer, A. Tal, S. Rusinkiewicz, and D. Dobkin. "Modeling by Example." ACM Transactions on Graphics 23(3), 609-612, 2004.）を改良した手法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する。これにより第３の要求条件を満たす特徴稜線が抽出できる。特徴稜線選択的抽出処理ＳＱ３は、領域分け処理ＳＱ２で抽出された特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させる。本実施の形態の３次元メッシュモデルの特徴稜線抽出装置では、これら３つの処理ＳＱ１〜ＳＱ３を、抽出パラメータ設定部５にて設定される異なる抽出パラメータ設定で数回繰り返し実行し、各パラメータ設定で抽出される特徴稜線群を対話的に集約する。
【００２９】
まず、頂点特徴量算出処理ＳＱ１について説明する。本実施の形態では、まず稜線の特徴量を算出し、この稜線特徴量をもとに頂点特徴量を算出する。稜線特徴量算出の最も単純な方法として、稜線を共有する２平面の２面角を計算する手法が考えられるが、この手法は２面角の値が大きなシャープな特徴稜線の抽出には有効だが、リバースエンジニアリングから得られるノイズを多く含んだメッシュモデルに対しては、局所的な形状に基づいた特徴量算出しか行っていないため、算出される特徴量がノイズの影響を受けやすく、隣接２平面の２面角の値が小さな特徴稜線の抽出は難しい。そこで本実施の形態では、稜線の近傍のユークリッド距離で定められる広域的な領域を評価し、特徴量を算出することで、この問題を解決する。図３は本実施の形態で実行する稜線特徴算出方法の説明図である。まず稜線ｅの中点を中心とする半径ｒの球Ｂを考える。次に、球Ｂに含まれる三角形の面法線ベクトルの和ｎ（バー）と稜線ｅとで定義した平面を用いて球Ｂを、２つの半球ＢＲ、ＢＬに分割する。次にＢＲ、ＢＬ内の各三角形面分の面積で重み付けした面法線ベクトルの和ｎＢＲ、ｎＢＬを数１式、数２式で計算する。
【数１】
【数２】
【００３０】
ここで、ｎｆは三角形面分ｆの単位面法線ベクトル、ＦＢＲ、ＦＢＬはＢＲ、ＢＬに含まれる三角形の集合、｜ｆ∩ＢＲ｜、｜ｆ∩ＢＬ｜はｆのＢＲ、ＢＬに含まれる部分の面積である。ただし、球や、球を分割した際に定義した平面と交差する三角形面分の球に含まれる部分の面積は、交差する部分を線分で置き換え、多角形で近似する。最後に面法線ベクトルｎＢＲ、ｎＢＬのなす角度を数３式で算出し、これを稜線ｅの特徴量θｅ（ｒ）とする。
【数３】
【００３１】
稜線特徴量θｅ（ｒ）の値が基本特徴稜線識別閾値τθより大きい稜線を基本特徴稜線、さらに基本特徴稜線の両端の頂点を基本特徴頂点と分類する。ここで、稜線の両端の頂点が基本特徴頂点であっても、必ずしもその稜線が基本特徴稜線とはならない。
【００３２】
次に、算出した稜線特徴量をもとに頂点特徴量を算出する。図４は頂点特徴算出のグラフであり、図５は各特徴量に基づく特徴稜線抽出結果の比較図である。それぞれ、（ａ）は連続特徴量、（ｂ）は離散特徴量、（ｃ）は差分特徴量を示している。まず頂点ｖに接続する稜線集合ｅ*（ｖ）内の稜線特徴量のうち、最も大きな稜線特徴量をｖの連続特徴量ｇｃｏｎ（ｖ）とする。
【数４】
【００３３】
数４式で得られる連続特徴量では、図４（ａ）のように本来１つの領域として認識したいフィレット面の頂点特徴量にばらつきが生じる。フィレットの開始位置にある頂点が小さい値を持ち、中央に近いほど大きな値を持ち、終了位置では開始位置と同じ小さい値を持つ。これをもとに後述する改良Ｗａｔｅｒｓｈｅｄ法を適用し領域分けを行うと、図５（ａ）のように、フィレット部が中央で２つに分割され、フィットの中央線が特徴稜線として抽出されてしまう。そこで図４（ｂ）のように、頂点特徴量離散化閾値τｖを用いてこの特徴量を離散化（２値化）したものをｇｄｉｓ（ｖ）とし、これによりフィレット面の頂点の特徴量を一定値にする。しかし、この離散特徴量では図５（ｂ）に示すように、Ｗａｔｅｒｓｈｅｄ法の性質上、抽出したいフィレット部はそれに滑らかに接続する片側の領域と同じ領域と認識され、フィレット面の片側の境界線しか抽出できない。そこで図４（ｃ）のように、頂点ｖの１近傍頂点との離散特徴量の差分を数５式で計算し、これを差分特徴量ｇｄｉｆ（ｖ）とする。これを用いることで図５（ｃ）に示すように、フィレット面の境界線が適切に抽出できる。
【数５】
【００３４】
ここでｖ＊はｖの隣接頂点集合である。本発明では、フィレット面の境界線抽出にのみ差分特徴量を、それ以外の特徴稜線抽出には連続特徴量を用いる。
【００３５】
次に、領域分け処理ＳＱ２について説明する。この演算処理では、改良したＷａｔｅｒｓｈｅｄ法を実行する。Ｗａｔｅｒｓｈｅｄ法は、画像の領域分け発明として提案された手法であり、画像処理の分野で今でも盛んに研究が行われている（非特許文献１２）。このＷａｔｅｒｓｈｅｄ法は、後に３次元メッシュモデルの領域分け手法に拡張された。非特許文献５では、水が高い所から低い所へ流れ落ちるように特徴量の大きい頂点から小さい頂点へとたどり、その過程でたどった頂点に共通の領域ラベルを割り当て、同じラベルを持つ頂点を１つの領域にグルーピングする手法が提案されている。
【００３６】
Ｗａｔｅｒｓｈｅｄ法は図６に示すように３つのステップからなる。図７は、Ｗａｔｅｒｓｈｅｄ法の概要を示す図であり、同図（ａ）がモデルの斜視図、同図（ｂ）が同図（ａ）の断面図、同図（ｃ）は同図（ａ）を展開し高さを特徴量とみなした曲線図、同図（ｄ）は頂点にラベルを割り当てた図、同図（ｅ）は同じ領域ラベルを持つ頂点をグルーピングした図、同図（ｆ）、（ｇ）は小さな領域を除去した図、同図（ｈ）は領域分けができなかった場合の図である。同図（ａ）では頂点特徴量を色分けしており、黒い頂点が大きい特徴量、白い頂点が小さい特徴量を持つ。
【００３７】
図６におけるステップＳＱ１１の局所最小値抽出処理は、図７（ｄ）に示すように、局所最小頂点抽出頂点特徴量が局所最小（その近傍の頂点がそれ自身より大きな特徴量を持つ）となる頂点集合を見つけ、それぞれの頂点に０から始まる固有の領域ラベルを割り当てる。
【００３８】
ステップＳＱ１２の降下処理は、図７（ｅ）に示すように、降下領域ラベルのない頂点をラベル付けされた領域（頂点集合）に到達するまで降下させ、その過程でたどった頂点すべてにその領域ラベルを割り当て、同じ領域ラベルを持つ頂点を１つの領域にグルーピングする。
【００３９】
ステップＳＱ１３の領域統合処理は次の通りである。ステップＳＱ１２で頂点集合からなる領域分けを行った際に、少ない数の頂点集合からなる小さな領域ができやすい。これらの領域の境界線として後に抽出される特徴稜線は、その利用の観点から見て好ましくなく、除去することが望ましい。そこでまず、領域内の最も低い連続特徴量を持つ頂点と、その領域の境界とその領域に隣接する領域の境界の頂点のうちの最も低い連続特徴量を持つ頂点ｖｂｏｕとの連続特徴量の差分を計算する。この差分をＷａｔｅｒｓｈｅｄ深さと呼ぶ。領域内の頂点数が領域内最小頂点数閾値τｎより少なく、かつ、Ｗａｔｅｒｓｈｅｄ深さが領域統合閾値τｄより小さい領域を、ｖｂｏｕに隣接する領域と統合する。この処理を上の条件を満たす領域がなくなるまで繰り返し、図７（ｆ）、図７（ｇ）のように小さな領域を除去する。
【００４０】
このＷａｔｅｒｓｈｅｄ法は頂点のみに領域ラベルを割り当て頂点集合からなる領域分けを行うため、３つの頂点の領域ラベルが一致せずどの領域にも属さない三角形集合からなる隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないといった問題点がある。また、図７（ｈ）に示すように認識すべき面分の内部に頂点がない（例えば、長方形が２つの直角三角形から構成される）場合に適切な領域分けができないといった問題点もある。
【００４１】
このような問題点を解決するため、非特許文献９に特徴稜線抽出精度向上のための改良を加えた改良Ｗａｔｅｒｓｈｅｄ法が提案されている。この手法では、Ｗａｔｅｒｓｈｅｄ法と三角形への領域ラベルの割り当てに基づき、三角形集合からなる領域分けが可能である。改良Ｗａｔｅｒｓｈｅｄ法は図８に示すように５つの処理ステップからなる。つまり、頂点追加処理のステップＳＱ２１、頂点特徴量算出のステップＳＱ２２、Ｗａｔｅｒｓｈｅｄ法による処理ステップＳＱ２３、頂点削除処理のステップＳＱ２４、そして面分への領域ラベル割り当て処理をするステップＳＱ２５である。
【００４２】
図９（ａ）は認識すべき面分の内部に頂点を含まないメッシュモデルの斜視図である。図９（ｂ）〜図９（ｇ）は、図９（ａ）の断面図を展開し、高さを特徴量とみなした曲線図である。この図では、線分はメッシュの三角形を表す。また、図１０は頂点追加の規則を説明する図である。
【００４３】
図８におけるステップＳＱ２１は、１つの領域として認識すべき面分集合内に頂点がない部分を適切に認識するため、メッシュ上の基本特徴稜線、図９（ｂ）の基本特徴頂点の分布状況に基づき、図９（ｃ）のように図１０に示す頂点追加規則に従って各辺の中点に頂点を追加する。
【００４４】
ステップＳＱ２２は、図９（ｄ）に示すように、追加した頂点のうち、基本特徴稜線上にある頂点には全頂点のうち最大特徴量を、三角形の面上にある頂点には全頂点のうち最小特徴量を、それ以外の頂点にはその頂点が追加された稜線の特徴量を定義する。
【００４５】
ステップＳＱ２３は、図９（ｅ）に示すように、頂点を追加したメッシュモデルにＷａｔｅｒｓｈｅｄ法を適用し各頂点に領域ラベルを割り当て、頂点集合からなる領域分けを行う。
【００４６】
ステップＳＱ２４は、図９（ｆ）に示すように、基本特徴頂点にそれら自身の領域ラベルとともに１近傍頂点の領域ラベルも付加した後、ステップＳＱ２１で追加した頂点をメッシュから削除する。これにより、基本特徴頂点は複数の領域ラベルを持つことになる。
【００４７】
ステップＳＱ２５は、図９（ｇ）に示すように、図１１の表に示す頂点ラベルの割り当て状況に従って各三角形に対して１つずつ領域ラベルを割り当てる。特にｃａｓｅ２〜ｃａｓｅ５は、ソリッドモデルのテセレーションなどにより得られる、１つの面分として認識したい領域内部に頂点を含まないために適切に領域分けできなかったメッシュモデルを領域分けする際に有効である。一方、ｃａｓｅ６は、リバースエンジニアリングから得られた高密度メッシュモデルにＷａｔｅｒｓｈｅｄ法を適用した場合に生じる隙間領域の三角形に適切に領域ラベルを割り当てる際に有効である。これによりすべての三角形に一つずつ領域ラベルが割り当てられ、同じ領域ラベルを持つ三角形群を１つの面分としてグルーピングする。
【００４８】
以上の５つのステップＳＱ２１〜ＳＱ２５により、メッシュモデルに対し連結三角形集合からなる領域分けを行い、最後に各領域の境界線を特徴稜線として抽出する。図１２は従来のＷａｔｅｒｓｈｅｄ法と、改良Ｗａｔｅｒｓｈｅｄ法を用いて領域分けを行った結果の比較図である。図１２（ａ）、（ｂ）は従来のＷａｔｅｒｓｈｅｄ法を用いた場合であり、同図（ｃ）、（ｄ）は改良Ｗａｔｅｒｓｈｅｄ法を用いた場合である。従来のＷａｔｅｒｓｈｅｄ法では、図１２（ａ）のように隣接領域間に隙間領域が生じ、その結果として、本来隣接領域の境界線として共有されるべき特徴稜線が共有されないといった問題点、さらに、図１２（ｂ）のように１つの面分として認識したい領域の内部に頂点がない場合に適切な領域分けができないといった問題点を持つことが分かる。これに対し、改良Ｗａｔｅｒｓｈｅｄ法を用いることで、これらの問題点が解決され、図１２（ｃ）のように特徴稜線が共有され、また図１２（ｄ）のように適切な領域分けができていることが確認できる。
【００４９】
次に、本実施の形態の装置にて実施する３次元メッシュモデルの特徴稜線抽出方法で用いる５つの抽出パラメータが、特徴稜線抽出に与える効果について説明する。この抽出パラメータは抽出パラメータ設定部５により行う。球の半径ｒは、稜線特徴量を算出する際の評価範囲を定めるために用いる。この値を小さくすると評価範囲が局所的になり、シャープな特徴稜線が抽出しやすくなり、大きくすると評価範囲が広域的になり、形状がなだらかに変化する部分にある特徴稜線が抽出しやすくなる。
【００５０】
頂点特徴量離散化閾値τｖは、フィレット面の境界線の抽出位置を調整する際に用いる。この値は、フィレット面の境界線上にある頂点が持つ特徴量に一致するよう、適切に設定する必要がある。この適切値より小さく設定すると、抽出したいフィレット面より広いフィレット面の境界線が抽出されてしまい、大きくすると抽出したいフィレット面より狭いフィレット面の境界線が抽出される。
【００５１】
基本特徴稜線識別閾値τθは、主にクリースエッジの抽出の際に用いる。大きくする設定すると隣接面との２面角が大きい面の境界線のみが抽出でき、この値を小さく設定すると隣接面との２面角が大きい面の境界線のみならず、小さい面の境界線もが抽出できる。
【００５２】
領域内最小頂点数閾値τｎこの値を小さく設定すると、少ない数の頂点集合からなる領域分けが行われ、その境界線が抽出でき、大きく設定すると、多い数の頂点集合からなる領域分けが行われ、その境界線のみ抽出できる。
【００５３】
領域統合閾値τｄは、この値を小さく設定すると、領域内の頂点特徴量の差が少ない領域分けが行われ、その境界線が抽出でき、大きくすると、領域内の頂点特徴量の差が大きい領域分けが行われ、その境界線のみ抽出できる。
【００５４】
上述した処理ＳＱ１の基本特徴稜線と基本特徴頂点に分類する手法を１通りのパラメータ設定で一度実行しただけでは、要求する特徴稜線のすべてを抽出することは困難である。そこで、以上の手法を異なる抽出パラメータ設定で繰り返し実行し、各抽出パラメータ設定で抽出される特徴稜線のうちのユーザの要求する稜線をディスプレイ上で対話的に選択し、集約することでこの問題を解決する。
【００５５】
本実施の形態の装置では、効率の良いユーザの特徴稜線抽出のために２つの特徴稜線選択手法を実装している。第１は、領域境界線ループの抽出である。これは、図１３（ａ）に示すように、領域内の面分の選択によって、領域境界のループをなす特徴稜線群を全て抽出する。第２は、区分特徴稜線の抽出である。これは、特徴稜線上のメッシュの稜線の選択によって、図１３（ｂ）に示すように３つ以上の特徴稜線が交わる頂点で境界付けられた区分的な特徴稜線を抽出する。これらを使い分けることで、あらゆる特徴稜線が選択的に集約でき、ユーザの要求する特徴稜線のみを抽出できる。
【００５６】
本実施の形態では、メッシュモデルからのソリッドモデルの自動生成を目的とした、広域的法線評価と改良Ｗａｔｅｒｓｈｅｄ法に基づく特徴稜線抽出が行える。
【実施例】
【００５７】
実験により、本発明を用いることで、メッシュに含まれるノイズやメッシュ分割方法の影響を受けにくく特徴稜線が抽出できること、またフィレット面の境界線を特徴稜線として抽出できること、抽出された特徴稜線がループをなし、それに囲まれる領域を１つの面分として認識できること、利用目的に応じた特徴稜線が選択的に抽出できることを確認した。また、抽出した特徴稜線の３次元ＣＡＤシステムへの読み込みも実現した。
【００５８】
図１４に、硬質ウレタンフォームで作られたＩＴ機器筐体モックアップ（ａ）を非接触測定器（Ｃｏｍｅｔ４００：商品名）で計測して得られた点群（約１４０万点）から三角形メッシュを生成した高密度メッシュモデル（ｂ）に対する特徴稜線抽出結果を示している。図１４（ｃ）、（ｅ）はそれぞれ異なる抽出パラメータで領域分けを行った結果である。同図（ｄ）、（ｆ）はそれぞれ、同図（ｃ）、（ｅ）の領域の境界線を特徴稜線として抽出した結果である。このような測定ノイズを多く含むメッシュモデルからも、抽出パラメータを適切に設定することで特徴稜線が抽出できることが確認できた。処理時間は、Ｘｅｏｎ２．４ＧＨｚ、メモリ２ＧＢのＰＣで１通りの抽出パラメータ設定での自動抽出処理に約６分（頂点特徴量算出に約５分、領域分けに基づく特徴稜線抽出に約１分）であった。
【００５９】
図１５に、ソリッドモデルを異なる分割方法で分割し得られたメッシュモデルに対する特徴稜線抽出結果を示している。図１５（ａ）の上段はＦＥＭメッシャにより分割して得られた高密度メッシュ、同図（ｂ）の上段はＦＥＭメッシャにより分割して得られた低解像度メッシュ、同図（ｃ）の上段はＳＴＬデータへの変換により得られたメッシュである。また、同図（ａ）〜（ｃ）の下段それぞれは、これらのメッシュモデルに対して本発明の特徴稜線抽出方法を何度か繰り返し実行し、特徴稜線を集約した結果である。図１５に示すように、分割方法の異なるメッシュモデルからも、ほぼ等しい特徴稜線が抽出できることが確認できた。図１５（ａ）、（ｂ）に関しては、メッシュの稜線はソリッドモデルを生成した際に定義した稜線上にある保障はない。それゆえ本来のソリッドモデル上の稜線に最も近いと思われる稜線を特徴稜線として抽出した結果、若干の誤差が見られた。
【００６０】
球の半径ｒの値は厳密に設定する必要はなく、例えば、物理モデルを測定して得られるノイズを多く含んだメッシュモデルに対しては、入力メッシュのＢｏｕｎｄｉｎｇＢｏｘの対角線の５０分の１〜１００分の１程度に設定すると良い結果が得られやすい。また、隣接２平面の２面角が大きいクリースエッジを多く含んだメッシュに対しては、ｒを小さな値に設定すると良い結果を得られやすい。また、図１４のように、頂点特徴量離散化閾値τｖを変更することで、径の小さなフィレット面、大きなフィレット面の境界線がそれぞれ抽出できることが確認できた。
【００６１】
図１６に、ユーザにより選択された特徴稜線の集約結果を示す。入力は、ソリッドモデルをＦＥＭメッシャにより分割して得られたひずみの小さい三角形からなるメッシュモデル（三角形数約６５、０００）である。図中の細い線がある抽出パラメータ設定で抽出されたすべての特徴稜線、太い線がユーザにより選択された特徴稜線である。図１６（ａ）〜（ｃ）の３通りの抽出パラメータ設定での特徴稜線の集約結果が図１６（ｄ）である。これより、異なる抽出パラメータ設定で抽出される特徴稜線が集約できることが分かる。処理時間は１通りの抽出パラメータ設定での自動抽出処理で、約４秒〜２６秒であった。
【００６２】
図１４〜図１６により、抽出された特徴稜線がループをなすこと、また、フィレット面の境界線が特徴稜線として抽出できていることが確認できた。
【００６３】
さらに、図１６のようにして得られた特徴稜線を３次元ＣＡＤシステム（ＳｏｌｉｄＷｏｒｋｓ：商品名）内に読み込んだ結果を図１７に示す。これより、集約された特徴稜線が３次元ＣＡＤシステムに正しく読み込まれていることが確認できた。
【図面の簡単な説明】
【００６４】
【図１】本発明の１つの実施の形態の３次元メッシュモデルの特徴稜線抽出装置のブロック図。
【図２】本発明の１つの実施の形態の３次元メッシュモデルの特徴稜線抽出装置が実行する３次元メッシュモデルの特徴稜線抽出プログラム及び方法のフローチャート。
【図３】上記実施の形態で実行される稜線特徴算出処理の説明図。
【図４】上記実施の形態で実行される頂点特徴算出処理のグラフ図。
【図５】上記実施の形態で抽出された特徴稜線の比較図。
【図６】Ｗａｔｅｒｓｈｅｄ法のシーケンス図。
【図７】Ｗａｔｅｒｓｈｅｄ法の説明図。
【図８】上記実施の形態で実行する改良Ｗａｔｅｒｓｈｅｄ法のシーケンス図。
【図９】上記実施の形態の改良Ｗａｔｅｒｓｈｅｄ法の説明図。
【図１０】上記実施の形態で採用した頂点追加規則の説明図。
【図１１】上記実施の形態で採用した頂点追加規則の表。
【図１２】従来のＷａｔｅｒｓｈｅｄ法と本実施の形態で実行する改良Ｗａｔｅｒｓｈｅｄ法とを用いて領域分けを行った結果の比較図。
【図１３】上記実施の形態で実行する特徴稜線の選択的抽出処理の説明図。
【図１４】本発明の実施例の特徴稜線抽出結果を示す図。
【図１５】本発明の実施例の物理モデルを異なる分割方法で分割し得られたメッシュモデルに対する特徴稜線抽出結果を示す図。
【図１６】本発明の実施例において複数の選択された特徴稜線の集約結果を示す図。
【図１７】図１６により得られた特徴稜線を３次元ＣＡＤシステム内に読み込んだ結果を示す図。
【符号の説明】
【００６５】
１ 頂点特徴量算出部
２領域分け処理部
３ 特徴稜線選択的抽出部
４記憶装置
５ 抽出パラメータ設定部
６ 演算処理制御部
７ 入出力処理部
８ キーボード
９ ポインティングデバイス
１０ ディスプレイ
【特許請求の範囲】
【請求項１】
諸データを保持する記憶手段と、
前記記憶手段に保持されている３次元メッシュモデルを呼び出し、稜線特徴量と頂点特徴量を算出する特徴量算出手段と、
前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する領域分け処理手段と、
前記領域分け処理手段の抽出した特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する特徴稜線選択的抽出手段とを備えた３次元メッシュモデルの特徴稜線抽出装置。
【請求項２】
前記特徴量算出手段は、前記記憶手段に保持されている３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、
前記領域分け処理手段は、前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とする請求項１に記載の３次元メッシュモデルの特徴稜線抽出装置。
【請求項３】
入力される若しくは記憶手段に保持されている３次元メッシュモデルのデータを呼び出す処理と、
前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出する処理と、
前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する処理と、
前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する処理とをコンピュータに実行させる３次元メッシュモデルの特徴稜線抽出プログラム。
【請求項４】
前記特徴量を算出する処理では、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、
前記特徴稜線を抽出する処理では、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とする請求項３に記載の３次元メッシュモデルの特徴稜線抽出プログラム。
【請求項５】
抽出パラメータと繰り返し回数を設定する処理を有し、
前記処理各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返し実行することを特徴とする請求項３又は４に記載の３次元メッシュモデルの特徴稜線抽出プログラム。
【請求項６】
入力される若しくは記憶手段に保持されている３次元メッシュモデルを呼び出すステップと、
前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出するステップと、
算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出するステップと、
前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力するステップとを有する３次元メッシュモデルの特徴稜線抽出方法。
【請求項７】
前記特徴量を算出するステップでは、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、
前記特徴稜線を抽出するステップでは、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とする請求項６に記載の３次元メッシュモデルの特徴稜線抽出方法。
【請求項８】
抽出パラメータと繰り返し回数を設定するステップを有し、
前記ステップ各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返すことを特徴とする請求項６又は７に記載の３次元メッシュモデルの特徴稜線抽出方法。
【請求項１】
諸データを保持する記憶手段と、
前記記憶手段に保持されている３次元メッシュモデルを呼び出し、稜線特徴量と頂点特徴量を算出する特徴量算出手段と、
前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する領域分け処理手段と、
前記領域分け処理手段の抽出した特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する特徴稜線選択的抽出手段とを備えた３次元メッシュモデルの特徴稜線抽出装置。
【請求項２】
前記特徴量算出手段は、前記記憶手段に保持されている３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、
前記領域分け処理手段は、前記特徴量算出手段の算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とする請求項１に記載の３次元メッシュモデルの特徴稜線抽出装置。
【請求項３】
入力される若しくは記憶手段に保持されている３次元メッシュモデルのデータを呼び出す処理と、
前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出する処理と、
前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出する処理と、
前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力する処理とをコンピュータに実行させる３次元メッシュモデルの特徴稜線抽出プログラム。
【請求項４】
前記特徴量を算出する処理では、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、
前記特徴稜線を抽出する処理では、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とする請求項３に記載の３次元メッシュモデルの特徴稜線抽出プログラム。
【請求項５】
抽出パラメータと繰り返し回数を設定する処理を有し、
前記処理各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返し実行することを特徴とする請求項３又は４に記載の３次元メッシュモデルの特徴稜線抽出プログラム。
【請求項６】
入力される若しくは記憶手段に保持されている３次元メッシュモデルを呼び出すステップと、
前記３次元メッシュモデルの稜線特徴量と頂点特徴量を算出するステップと、
算出した頂点特徴量に基づいて、前記３次元メッシュモデルに対して連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出するステップと、
前記特徴稜線のうち、ユーザの要求する特徴稜線のみを対話的に選択させ、選択された特徴稜線のデータを出力するステップとを有する３次元メッシュモデルの特徴稜線抽出方法。
【請求項７】
前記特徴量を算出するステップでは、前記３次元メッシュモデルに対して、ユークリッド距離で定めた領域内の三角形集合の法線を広域的に評価することにより稜線特徴量と頂点特徴量を算出し、
前記特徴稜線を抽出するステップでは、前記頂点特徴量に基づいて、前記３次元メッシュモデルに対して改良Ｗａｔｅｒｓｈｅｄ法を用いて連結三角形集合からなる領域分けを行い、この領域の境界線を特徴稜線として抽出することを特徴とする請求項６に記載の３次元メッシュモデルの特徴稜線抽出方法。
【請求項８】
抽出パラメータと繰り返し回数を設定するステップを有し、
前記ステップ各々を、設定された抽出パラメータを用いて設定された繰り返し回数だけ繰り返すことを特徴とする請求項６又は７に記載の３次元メッシュモデルの特徴稜線抽出方法。
【図１】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００６−２７７７１３（Ｐ２００６−２７７７１３Ａ）
【公開日】平成１８年１０月１２日（２００６．１０．１２）
【国際特許分類】
【出願番号】特願２００５−２１１９５５（Ｐ２００５−２１１９５５）
【出願日】平成１７年７月２１日（２００５．７．２１）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１６年９月１日 社団法人精密工学会発行の「２００４年度 精密工学会秋季大会 学術講演会講演論文集」に発表
【出願人】（５０４１７３４７１）国立大学法人 北海道大学 (971)
【Ｆターム（参考）】
【公開日】平成１８年１０月１２日（２００６．１０．１２）
【国際特許分類】
【出願日】平成１７年７月２１日（２００５．７．２１）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成１６年９月１日 社団法人精密工学会発行の「２００４年度 精密工学会秋季大会 学術講演会講演論文集」に発表
【出願人】（５０４１７３４７１）国立大学法人 北海道大学 (971)
【Ｆターム（参考）】
[ Back to top ]