(57)【特許請求の範囲】
【請求項１】
与えられた曲面をポリゴン化して近似的に表現する複数の元の三角形を細分化することにより、それら複数の元の三角形の集合により形成される近似ポリゴン表面をスムース化する方法であって、細分化に先立ち、その細分化により発生させるべき複数の三角形の複数の頂点であって元の三角形にはない新規頂点を、その元の三角形の各辺の両端における２つの頂点と、それら２つの頂点の各々における法線ベクトルである２つの頂点法線ベクトルとに基づき、その辺上にではなく、その辺が近似すべき曲線要素上に発生させる近似ポリゴン表面スムース化方法であって、
メモリが、前記複数の元の三角形のデータを記憶し、
プロセッサが、そのメモリに記憶されているデータに基づいて、前記２つの頂点の各々に関し、前記複数の元の三角形のうちそれら各頂点を共有するものを抽出するステップと、
プロセッサが、その抽出した複数の元の三角形に関し、元の三角形の３つの頂点に基づいてその元の三角形の面に対する法線ベクトルを複数の面法線ベクトルとして取得するステップと、
プロセッサが、その取得した複数の面法線ベクトルに基づいて前記頂点法線ベクトルを、前記２つの頂点についてそれぞれ決定し、その決定に際して、各面法線ベクトルの影響を頂点法線ベクトルに、各面法線ベクトルに対応する前記元の三角形の前記共有頂点における角度が大きいほど強く及ぼさせるステップと、
プロセッサが、その決定した２つの頂点法線ベクトルと前記２つの頂点とに基づいて前記曲線要素を取得するステップと、
プロセッサが、その取得した曲線要素上に前記新規頂点を発生させるステップと
を含むことを特徴とする近似ポリゴン表面スムース化方法。
【請求項２】
前記プロセッサが、前記複数の面法線ベクトルに基づいて前記複数の元の三角形について前記２つの頂点法線ベクトルを決定した後に、それら決定した２つの頂点法線ベクトルの各々を、それら各頂点法線ベクトルと同様にして決定されてそれら各頂点法線ベクトルに隣接する他の複数の頂点法線ベクトルの少なくとも一つに基づいて修正するステップを含む請求項１に記載の近似ポリゴン表面スムース化方法。
【請求項３】
前記プロセッサが、前記複数の元の三角形の各辺が互いに接続されることによって構成される複数の構成線の少なくとも一つを特徴線として取得するステップを含み、かつ、前記プロセッサが前記頂点法線ベクトルを２つの頂点についてそれぞれ決定するステップが、前記頂点法線ベクトルを決定すべき頂点がその取得した特徴線上にない場合には、その頂点を共有するすべての元の三角形の面法線ベクトルに基づいて前記頂点法線ベクトルを決定し、一方、その取得した特徴線上にある場合には、その特徴線の一側に位置する少なくとも一つの元の三角形の面法線ベクトルに基づいて第１の頂点法線ベクトル、他側に位置する少なくとも一つの元の三角形の面法線ベクトルに基づいて第２の頂点法線ベクトルをそれぞれ決定するステップを含む請求項１または２に記載の近似ポリゴン表面スムース化方法。
【請求項４】
前記複数の元の三角形のうち同じ辺を共有する２つの元の三角形を抽出し、その抽出した２つの元の三角形がその共有辺において接続される角度が基準値より小さい場合には、その共有辺を前記特徴線として抽出する一方、基準値以上である場合には、抽出しない工程を含む請求項３に記載の近似ポリゴン表面スムース化方法。
【請求項５】
前記プロセッサが２つの頂点法線ベクトルと２つの頂点とに基づいて曲線要素を取得するステップが、
(a) 取得すべき前記曲線要素に対応する前記辺に対して、それの両端点の一方である第１端点を始点、他方である第２端点を終点とする第１関数と、第２端点を始点、第１端点を終点とする第２関数とを定義するステップと、
(b) 前記第１関数と、前記第１端点における前記頂点法線ベクトルである第１頂点法線ベクトルとの積を第１端点から辺上の任意点まで積分した値を、第１関数の下で前記辺に対応する第１曲線要素を取得するために辺上の任意点を移動させる向きと量とを表す第１移動ベクトルとするステップと、
(c) 前記第２関数と、前記第２端点における前記頂点法線ベクトルである第２頂点法線ベクトルとの積を第２端点から辺上の任意点まで積分した値を、第２関数の下で前記辺に対応する第２曲線要素を取得するために辺上の任意点を移動させる向きと量とを表す第２移動ベクトルとするステップと、
(d) それら第１および第２移動ベクトルの和として、前記辺に対応する最終曲線要素を取得するステップであって、前記第１関数および前記第２関数の各々が、
(i)  前記辺上を始点から終点まで移動するにつれて０から辺の長さＬまで変化する変数ｔを有し、
(ii)  その変数ｔに関して０から辺の長さＬまで積分した値が０となり、
(iii)  前記変数ｔが０のときに値ｈ、変数ｔが辺の長さの半値Ｌ／２のときに大きさが値ｈの半分であって符号が値ｈとは逆である値−ｈ／２、変数ｔが辺の長さＬのときに０となり、
(iv)  前記値ｈが、前記最終曲線要素が第１および第２端点において前記第１および第２頂点法線ベクトルとそれぞれ直交するように設定されているステップと
を含む請求項１ないし４のいずれかに記載の近似ポリゴン表面スムース化方法。
【請求項６】
前記第１関数および前記第２関数の各々が、横軸に前記変数ｔ、縦軸に各関数の値が取られた座標面において、変数ｔが０であり、かつ、関数値が前記値ｈである点と、変数ｔが前記半値Ｌ／２であり、かつ、関数値が前記値−ｈ／２である点と、変数ｔが前記長さＬであり、かつ、関数値が０である点とを相互に１本の直線でつないだグラフで表される関係を定義するものである請求項５に記載の近似ポリゴン表面スムース化方法。
【請求項７】
前記プロセッサが、前記細分化に先立ち、前記元の三角形の各辺とそれに対応する前記曲線要素との隔たりが基準値より大きい場合には、その辺に関して前記新規頂点を発生させる一方、基準値以下である場合には、発生させない請求項１ないし６のいずれかに記載の近似ポリゴン表面スムース化方法。
【請求項８】
前記プロセッサが、前記細分化に先立ち、前記曲面のうち作業者により指定された領域内においては、前記元の三角形の各辺とそれに対応する前記曲線要素との隔たりが第１基準値より大きい場合には、その辺に関して前記新規頂点を発生させる一方、第１基準値以下である場合には、発生させず、指定された領域外においては、前記隔たりが第２基準値より大きいか否かを問わず、すべての前記辺に関して前記新規頂点を発生させる請求項１ないし６のいずれかに記載の近似ポリゴン表面スムース化方法。
【請求項９】
前記プロセッサが、前記細分化を、前記曲面のうち作業者により指定された領域内においてのみ行う請求項１ないし６のいずれかに記載の近似ポリゴン表面スムース化方法。
【請求項１０】
請求項１ないし９のいずれかに記載の近似ポリゴン表面スムース化方法を実施するためにコンピュータにより実行されるプログラムが記録されたことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、与えられた曲面をポリゴン化して近似的に表現する複数の元の三角形を細分化することにより、それら複数の元の三角形の集合により形成される近似ポリゴン表面をスムース化する技術に関するものである。
【０００２】
【従来の技術】
特開平８−２６３６９２号公報には、細分化に先立ち、その細分化により発生させるべき複数の三角形の頂点であって元の三角形にはない新規頂点を、その元の三角形の各辺の両端における２つの頂点と、それら２つの頂点の各々における法線ベクトルである２つの頂点法線ベクトルとに基づき、その辺上にではなく、その辺が近似すべき曲線要素上に発生させる技術が記載されている。
また、この公報には、頂点法線ベクトルを決定する方法に関し、『例えば、ＣＴ  Ｘ線断層撮影装置又はＭＲ装置のような画像補捉測定装置１は、検査されるべき対象物の多数の断層画像又は３次元画像を形成する。上記画像に基づいて、画像処理装置２は、多数の三角形によって対象物の面を近似的に表す物体モデルを形成する。上記三角形の頂点の位置情報と、上記頂点における上記対象物の面に対する法線は、画像メモリ３に記憶される。』と記載されている。
【０００３】
【発明が解決しようとする課題，課題解決手段，作用および発明の効果】
しかし、この公報は、『上記頂点における上記対象物の面に対する法線』、すなわち、前記頂点法線ベクトルを決定する方法を具体的に教えてはいない。
一方、頂点法線ベクトルを利用する近似ポリゴン表面スムース化方法においては、頂点法線ベクトルが、容易に決定できるとともに、真のもの、すなわち、与えられた曲面に対する法線ベクトルであって頂点を通過するものにできる限り一致するように精度よく決定できることが望ましい。
【０００４】
本発明は、以上の事情を背景として、頂点法線ベクトルを容易にかつ精度よく決定することにより、与えられた曲面を容易にかつ精度よく再現し得る近似ポリゴン表面スムース化方法を提供することを課題としてなされたものである。
【０００５】
その課題は下記態様によって解決される。なお、以下の説明において、本発明の各態様を、それぞれに項番号を付して請求項と同じ形式で記載する。
【０００６】
(1) 与えられた曲面をポリゴン化して近似的に表現する複数の元の三角形を細分化することにより、それら複数の元の三角形の集合により形成される近似ポリゴン表面をスムース化する方法であって、細分化に先立ち、その細分化により発生させるべき複数の三角形の複数の頂点であって元の三角形にはない新規頂点を、その元の三角形の各辺の両端における２つの頂点と、それら２つの頂点の各々における法線ベクトルである２つの頂点法線ベクトルとに基づき、その辺上にではなく、その辺が近似すべき曲線要素上に発生させる近似ポリゴン表面スムース化方法であって、
メモリが、前記複数の元の三角形のデータを記憶し、
プロセッサが、そのメモリに記憶されているデータに基づいて、前記２つの頂点の各々に関し、前記複数の元の三角形のうちそれら各頂点を共有するものを抽出するステップと、
プロセッサが、その抽出した複数の元の三角形に関し、元の三角形の３つの頂点に基づいてその元の三角形の面に対する法線ベクトルを複数の面法線ベクトルとして取得するステップと、
プロセッサが、その取得した複数の面法線ベクトルに基づいて前記頂点法線ベクトルを、前記２つの頂点についてそれぞれ決定し、その決定に際して、各面法線ベクトルの影響を頂点法線ベクトルに、各面法線ベクトルに対応する前記元の三角形の前記共有頂点における角度が大きいほど強く及ぼさせるステップと、
プロセッサが、その決定した２つの頂点法線ベクトルと前記２つの頂点とに基づいて前記曲線要素を取得するステップと、
プロセッサが、その取得した曲線要素上に前記新規頂点を発生させるステップと
を含むことを特徴とする近似ポリゴン表面スムース化方法〔請求項１〕。
本発明者らは、元の三角形の３つの頂点の位置が判れば元の三角形の面に対する法線ベクトルである面法線ベクトルを取得でき、また、同じ頂点を共有する複数の元の三角形について面法線ベクトルが分かれば頂点法線ベクトルを決定できることに気がついた。また、面法線ベクトルは、与えられた曲面のうち元の三角形が近似すべき曲面要素に対する代表的な法線ベクトルと十分に一致すると考えられるため、面法線ベクトルを用いて頂点法線ベクトルを決定することは、結果的に曲面要素に対する法線ベクトルであってその頂点を通過するものを考慮して頂点法線ベクトルが決定されることになることにも気がついた。
以上の知見に基づき、本項に記載の方法においては、同じ頂点を共有する複数の元の三角形に関し、元の三角形の３つの頂点に基づいてその元の三角形の面法線ベクトルが取得され、それら複数の元の三角形について取得された複数の面法線ベクトルに基づいてその頂点における頂点法線ベクトルが決定される。
したがって、この方法によれば、頂点法線ベクトルを容易にかつ精度よく決定でき、その結果、与えられた曲面を容易にかつ精度よく再現できる。
しかも、各面法線ベクトルの影響が、決定すべき頂点法線ベクトルに、同じ頂点を共有する複数の元の三角形の間で常に互いに等しい強さで及ぼされるのではなく、その共有頂点の角度が大きい三角形ほど、その三角形に対応する面法線ベクトルの影響が、決定すべき頂点法線ベクトルに強く及ぼされる。そのため、頂点法線ベクトルを真のもの、すなわち、与えられた曲面に対する法線ベクトルであって頂点を通過するものにより近いものとして決定できる。
(2) 前記プロセッサが、前記複数の面法線ベクトルに基づいて前記複数の元の三角形について前記２つの頂点法線ベクトルを決定した後に、それら決定した２つの頂点法線ベクトルの各々を、それら各頂点法線ベクトルと同様にして決定されてそれら各頂点法線ベクトルに隣接する他の複数の頂点法線ベクトルの少なくとも一つに基づいて修正するステップを含む (1)項に記載の近似ポリゴン表面スムース化方法〔請求項２〕。
この方法によれば、隣接する他の複数の頂点法線ベクトルを全く考慮しないで頂点法線ベクトルを決定する場合に比較して、互いに近接する複数の頂点法線ベクトルが向きが互いにより連続性を有するように決定できる。
(3) 前記プロセッサが、前記複数の元の三角形の各辺が互いに接続されることによって構成される複数の構成線の少なくとも一つを特徴線として取得するステップを含み、かつ、前記プロセッサが前記頂点法線ベクトルを２つの頂点についてそれぞれ決定するステップが、前記頂点法線ベクトルを決定すべき頂点がその取得した特徴線上にない場合には、その頂点を共有するすべての元の三角形の面法線ベクトルに基づいて前記頂点法線ベクトルを決定し、一方、その取得した特徴線上にある場合には、その特徴線の一側に位置する少なくとも一つの元の三角形の面法線ベクトルに基づいて第１の頂点法線ベクトル、他側に位置する少なくとも一つの元の三角形の面法線ベクトルに基づいて第２の頂点法線ベクトルをそれぞれ決定するステップを含む (1)項または (2)項に記載の近似ポリゴン表面スムース化方法（請求項３〕。
与えられた曲面においてある線を境界とする２部分の面の向きが互いに大きく異なる場合、その境界上の頂点における頂点法線ベクトルを、境界の両側に位置する複数の面法線ベクトルに基づいて決定すると、最終的に、それら２部分の面間の角度が小さくなるように近似ポリゴン表面のスムース化が行われてしまう。このような事態を容認したのでは、近似ポリゴン表面の再現性を低下させることになる。
これに対して、本項に記載の方法においては、境界上の頂点については、境界の一側と他側とで互いに独立して頂点法線ベクトルがそれぞれ決定される。
したがって、この方法によれば、曲面のうち２部分の面の向きが互いに大きく異なる部分についても、頂点法線ベクトルを適正に決定できる。
(4) 前記複数の元の三角形のうち同じ辺を共有する２つの元の三角形を抽出し、その抽出した２つの元の三角形がその共有辺において接続される角度が基準値より小さい場合には、その共有辺を前記特徴線として抽出する一方、基準値以上である場合には、抽出しない工程を含む (3)項に記載の近似ポリゴン表面スムース化方法〔請求項４〕。
この方法において「特徴線の抽出」は、作業者により行っても、コンピュータにより行ってもよい。
(5) 前記プロセッサが２つの頂点法線ベクトルと２つの頂点とに基づいて曲線要素を取得するステップが、
(a) 取得すべき前記曲線要素に対応する前記辺に対して、それの両端点の一方である第１端点を始点、他方である第２端点を終点とする第１関数と、第２端点を始点、第１端点を終点とする第２関数とを定義するステップと、
(b) 前記第１関数と、前記第１端点における前記頂点法線ベクトルである第１頂点法線ベクトルとの積を第１端点から辺上の任意点まで積分した値を、第１関数の下で前記辺に対応する第１曲線要素を取得するために辺上の任意点を移動させる向きと量とを表す第１移動ベクトルとするステップと、
(c) 前記第２関数と、前記第２端点における前記頂点法線ベクトルである第２頂点法線ベクトルとの積を第２端点から辺上の任意点まで積分した値を、第２関数の下で前記辺に対応する第２曲線要素を取得するために辺上の任意点を移動させる向きと量とを表す第２移動ベクトルとするステップと、
(d) それら第１および第２移動ベクトルの和として、前記辺に対応する最終曲線要素を取得するステップであって、前記第１関数および前記第２関数の各々が、
(i)  前記辺上を始点から終点まで移動するにつれて０から辺の長さＬまで変化する変数ｔを有し、
(ii)  その変数ｔに関して０から辺の長さＬまで積分した値が０となり、
(iii)  前記変数ｔが０のときに値ｈ、変数ｔが辺の長さの半値Ｌ／２のときに大きさが値ｈの半分であって符号が値ｈとは逆である値−ｈ／２、変数ｔが辺の長さＬのときに０となり、
(iv)  前記値ｈが、前記最終曲線要素が第１および第２端点において前記第１および第２頂点法線ベクトルとそれぞれ直交するように設定されているステップと
を含む (1)項ないし (4)項のいずれかに記載の近似ポリゴン表面スムース化方法〔請求項５〕。
この方法によれば、曲線要素を、その形状の種類を問わず、同じ種類の関数によって表現でき、よって、曲線要素の形状の種類に対して汎用性が高い近似ポリゴン表面スムース化方法が得られる。
(6) 前記第１関数および前記第２関数の各々が、横軸に前記変数ｔ、縦軸に各関数の値が取られた座標面において、変数ｔが０であり、かつ、関数値が前記値ｈである点と、変数ｔが前記半値Ｌ／２であり、かつ、関数値が前記値−ｈ／２である点と、変数ｔが前記長さＬであり、かつ、関数値が０である点とを相互に１本の直線でつないだグラフで表される関係を定義するものである (5)項に記載の近似ポリゴン表面スムース化方法〔請求項６〕。
この方法によれば、前項の記載の関数として使い勝手のよいものを使用できる。
(7) 前記プロセッサが、前記細分化に先立ち、前記元の三角形の各辺とそれに対応する前記曲線要素との隔たりが基準値より大きい場合には、その辺に関して前記新規頂点を発生させる一方、基準値以下である場合には、発生させない (1)項ないし (6)項のいずれかに記載の近似ポリゴン表面スムース化方法〔請求項７〕。
この方法においては、複数の元の三角形の複数の辺のうち、辺の細分化（新規頂点の発生）が必要でないものについては辺の細分化が省略される。したがって、この方法によれば、無駄な辺の細分化を回避できる。
この方法において「元の三角形」は、細分化の対象となる三角形を意味する。よって、「元の三角形」は、最初の細分化に際しては最初の三角形を意味し、再度の細分化に際してはその細分化の直前に存在する三角形を意味することとなる。
(8) 前記プロセッサが、前記細分化に先立ち、前記曲面のうち作業者により指定された領域内においては、前記元の三角形の各辺とそれに対応する前記曲線要素との隔たりが第１基準値より大きい場合には、その辺に関して前記新規頂点を発生させる一方、第１基準値以下である場合には、発生させず、指定された領域外においては、前記隔たりが第２基準値より大きいか否かを問わず、すべての前記辺に関して前記新規頂点を発生させる (1)項ないし (6)項のいずれかに記載の近似ポリゴン表面スムース化方法〔請求項８〕。
この方法によれば、例えば、第１基準値を第２基準値より小さく設定し、それにより、指定領域の内側において外側におけるより細かな辺の細分化を行おうとする場合に、指定領域内において、細かな辺の細分化が無駄に行われてしまうことを回避できる。
(9) 前記プロセッサが、前記細分化を、前記曲面のうち作業者により指定された領域内においてのみ行う (1)項ないし (6)項のいずれかに記載の近似ポリゴン表面スムース化方法〔請求項９〕。
(10)  (1)項ないし (9)項のいずれかに記載の近似ポリゴン表面スムース化方法を実施するためにコンピュータにより実行されるプログラムが記録されたことを特徴とするコンピュータ読み取り可能な記録媒体〔請求項１０〕。
ここにおける「記録媒体」には例えば、フレキシブルディスク，磁気テープ，磁気ディスク，磁気ドラム，磁気カード，光ディスク，光磁気ディスク，ＲＯＭ，ＣＤ−ＲＯＭ，ＩＣカード，穿孔テープ等がある。
【０００７】
【発明の実施の形態】
以下、本発明のいくつかの実施の形態である近似ポリゴン表面スムース化方法を図面に基づいて詳細に説明する。
【０００８】
まず、第１実施形態を説明する。
図１には、本実施形態を実施するのに使用されるデータ処理システムが示されている。このシステムにおいては、コンピュータ１０に入力装置１２，出力装置１４，表示装置１６および外部記憶装置１８が接続されている。コンピュータ１０は、プロセッサ２０およびメモリ２２を備えている。入力装置１２は、キーボード，マウス，デジタイザ等により構成される。出力装置１４は、プリンタ，プロッタ等により構成される。表示装置１６は、ＣＲＴ，液晶ディスプレイ等により構成される。外部記憶装置１８は、可搬な記録媒体２４に対してデータの読み込みと書き込みとを行う部分を含むように構成される。記録媒体２４には、コンピュータ１０により実行されるアプリケーションプログラムとしての近似ポリゴン表面スムース化プログラム（以下、単に「スムース化プログラム」という）が記録されるとともに、そのスムース化プログラムが実行される対象としてのＳＴＬ（ステレオリソグラフィ）データが記録されている。
【０００９】
ＳＴＬデータは、光造形方法により製造すべき３次元モデルの形状を表現するための標準的なデータとして知られている。ＳＴＬデータは、与えられた曲面を複数の三角形の集合により近似的に表現するデータであり、各々三角形に関する情報を表す複数の三角形データを含んでいる。各三角形データは、属性として、
▲１▼三角形の番号である三角形番号を表すデータと、
▲２▼三角形の３辺の各々の番号である辺番号を表すデータと、
▲３▼各辺の両端点の座標値である端点座標値を表すデータと、
▲４▼それら三角形番号，辺番号および端点座標値間の関連を表すデータと
を有している。ただし、ＳＴＬデータは、各三角形とそれが隣接する他の三角形との関係である隣接関係を直接に規定する隣接関係規定データを有してはいない。
【００１０】
作業者は、コンピュータ１０の電源を投入した後、近似ポリゴン表面スムース化の実行指令を入力するとともに、その実行対象であるＳＴＬデータを指定する。それに応じて、外部記憶装置１８が記録媒体２４から、上記スムース化プログラムとＳＴＬデータとを読み出してメモリ２２にストアする。その後、プロセッサ２０はスムース化プログラムをメモリ２２から読み出してＳＴＬデータを対象として実行する。
【００１１】
スムース化プログラムが実行されると、まず、図２のステップＳ１（以下、単に「Ｓ１」で表す。他のステップについても同じ）において、ＳＴＬデータに上記隣接関係規定データが付加される。具体的には、まず、複数の元の三角形の各々がそれの三角形番号に従って順に対象三角形とされ、次に、その対象三角形がそれの各辺において隣接する他の元の三角形である隣接三角形が求められ、続いて、対象三角形の各辺の辺番号と、隣接三角形の三角形番号と、その隣接三角形の３辺のうち対象三角形と共有する共有辺の辺番号とが互いに関連付けられたデータが隣接関係規定データとしてメモリ２２にストアされる。隣接関係規定データの付加によってＳＴＬデータの構造が変化する様子を概念的に可視化して説明すれば、隣接関係規定データの付加前は、図３の(a) に示すように、複数の三角形データが直接には互いに関連付けられずにばらばらに存在していたが、隣接関係規定データの付加後は、同図の(b) に示すように、複数の三角形データが直接に互いに関連付けられることになる。
【００１２】
次に、Ｓ２において、複数の元の三角形の複数の辺の中から、ＳＴＬデータにより表現すべき曲面の形状を特徴付けるものが特徴線として抽出される。具体的には、同じ辺において互いに接続される２つの元の三角形の面が成す角度が基準値より小さい場合に、その辺が特徴線として抽出される。図４の例では、辺１００において互いに接続される２つの元の三角形１０２，１０４の接続角度が基準値より小さいため、辺１００が特徴線として抽出される。同様にして、辺１０６において互いに接続される２つの元の三角形１０８，１１０の接続角度が基準値より小さいため、辺１０６が特徴線として抽出される。結局、この例においては、２本の閉じた太い実線で示す複数の辺が特徴線として抽出される。なお、２つの元の三角形の接続角度は、それら２つの元の三角形の内側における角度として定義でき、また、その場合、基準値を１００〜１２０度に設定できる。
【００１３】
続いて、Ｓ３において、複数の元の三角形の複数の頂点の各々について頂点法線ベクトルが決定される。このステップの詳細が図５に頂点法線ベクトル決定ルーチンとしてフローチャートで表されている。
【００１４】
本ルーチンにおいては、まず、Ｓ１１において、複数の元の三角形の複数の頂点の各々が順に対象頂点に決定され、次に、Ｓ１２において、複数の元の三角形の中から、その決定された対象頂点を共有する複数の元の三角形が抽出される。続いて、Ｓ１３において、抽出された複数の元の三角形の各々の３つの頂点の位置データがメモリ２２から読み込まれ、その読み込まれた位置データに基づき、その複数の元の三角形の各々の面に対する法線ベクトルである面法線ベクトルが取得される。具体的には、元の三角形の３つの頂点を含む一平面が取得され、その取得された一平面に直交する単位ベクトルとして面法線ベクトルが取得される。
【００１５】
その後、Ｓ１４において、今回の対象頂点が、前記抽出された特徴線上にないか否かが判定される。今回はないと仮定すれば、判定がＹＥＳとなり、Ｓ１５において、その対象頂点について１つの頂点法線ベクトルが決定される。具体的には、抽出された複数の元の三角形に対応する複数の面法線ベクトルの加重平均が１つの頂点法線ベクトルに決定される。加重平均における重みは、各面法線ベクトルが対応する元の三角形の３つの頂点のうち対象頂点と一致するものの角度が大きいほど、大きく設定されている。
【００１６】
図６の(a) には、対象頂点が特徴線上にない場合の一例が示されている。この場合、対象頂点１２０を共有する複数の元の三角形１２２，１２４，１２６，１２８，１３０の全ての面法線ベクトル１３２，１３４，１３６，１３８，１４０の加重平均として１つの頂点法線ベクトル１４２が決定される。
【００１７】
これに対して、今回の対象頂点が、前記抽出された特徴線上にある場合には、Ｓ１４の判定がＮＯとなり、Ｓ１６において、その対象頂点について２つの頂点法線ベクトル、すなわち、第１および第２頂点法線ベクトルが決定される。具体的には、対象頂点を共有する複数の元の三角形が、その特徴線に関して一側にあるグループと他側にあるグループとに分けられ、各グループ毎に頂点法線ベクトルが、Ｓ１５におけると同様にして決定される。第１頂点法線ベクトルは、特徴線の一側にある元の三角形のグループ、第２頂点法線ベクトルは、特徴線の他側にある元の三角形のグループにそれぞれ対応して決定される。
【００１８】
図６の(b) には、対象頂点が特徴線上にある場合の一例が示されている。この場合、特徴線１５０上にある対象頂点１５２に関して、元の三角形１５４，１５６，１５８が第１グループ、元の三角形１６０，１６２が第２グループを構成する。そして、第１グループに属する３つの元の三角形１５４，１５６，１５８の３つの面法線ベクトルの加重平均として第１頂点法線ベクトル１６４が決定され、一方、第２グループに属する２つの元の三角形１６０，１６２の２つの面法線ベクトルの加重平均として第２頂点法線ベクトル１６６が決定される。
【００１９】
いずれの場合にも、その後、Ｓ１７において、全ての頂点について頂点法線ベクトルが決定されたか否かが判定される。今回は、そうではないと仮定すれば、判定がＮＯとなり、Ｓ１１に戻り、新たな頂点が対象頂点に決定されて以下のステップが前記の場合と同様に実行される。これに対して、全ての頂点について頂点法線ベクトルが決定されたと仮定すれば、Ｓ１７の判定がＹＥＳとなり、Ｓ１８に移行する。
【００２０】
Ｓ１８においては、決定された複数の頂点法線ベクトルが順に対象頂点法線ベクトルに決定されるとともに、対象頂点法線ベクトルの向きが、隣接する他の少なくとも一つの頂点法線ベクトルの向きを考慮して修正される。隣接する他の少なくとも一つの頂点法線ベクトルは、他の複数の頂点法線ベクトルのうち、通過する頂点が、対象頂点法線ベクトルが通過する頂点を中心として半径が設定値である球内に存在するものとして抽出される。また、隣接する他の少なくとも一つの頂点法線ベクトルのうち、それが通過する頂点と対象頂点法線ベクトルが通過する頂点との距離が短いものほど、対象頂点法線ベクトルに強い影響を及ぼすように修正される。このようにすることにより、複数の頂点法線ベクトル間で向きの連続性が向上させられることになる。以上で本ルーチンの一回の実行が終了する。
【００２１】
以上のようにしてＳ３が終了すれば、続いて、図２のＳ４において、三角形が細分化される。本ステップの詳細が図７に三角形細分化ルーチンとしてフローチャートで表されている。
【００２２】
まず、Ｓ３１において、複数の元の三角形の複数の辺が順に対象辺とされるとともに、その対象辺について山谷関数ｆ(t) が定義される。山谷関数ｆ(t) は、図８に示すように、下に凸の折れ線のグラフで表される。図において、「Ｌ」は、対象辺の長さを表しており、また、「ｔ」は、対象辺上を始点Ｐ0 から終点ＰL まで移動するにつれて０からＬまで変化する変数である。この山谷関数ｆ(t) は、上記長さＬと値ｈとが設定されれば、唯一に特定される。長さＬは、その対象辺の両端における２つの頂点に基づいて設定される。値ｈの設定については後述する。
【００２３】
この山谷関数ｆ(t) は、ｔ＝０〜Ｌを積分区間として積分すると、０になるように定義される。また、その山谷関数ｆ(t) と頂点法線ベクトルＮとの積をｔ＝０〜ｔ（０≦ｔ≦Ｌ）を積分区間として積分したもの、すなわち、
∫Ｎ・ｆ(t) dt
は、図９に示すように、対象辺Ｓ上の任意点Ｐt が、対象辺Ｓから曲線要素Ｃに到達するまでに移動する向きおよび量を示す移動ベクトルＸt である。その向きはもちろん、頂点法線ベクトルＮに平行である。図の例においては、Ｘt1は任意点Ｐt1の移動ベクトル、Ｘt2は任意点Ｐt2の移動ベクトルを示している。
【００２４】
山谷関数ｆ(t) は、対象辺Ｓの第１端点Ｑ1 を始点Ｐ0 、第２端点Ｑ2 を終点ＰL とする第１山谷関数ｆ1 (t) と、第２端点Ｑ2 を始点Ｐ0 、第１端点Ｑ1 を終点ＰL とする第２山谷関数ｆ2 (t) とを含んでいる。図１０には、それら第１および第２山谷関数ｆ1 (t) ，ｆ2 (t) により表される第１および第２曲線要素Ｃ1 ，Ｃ2 がそれぞれ示されている。
【００２５】
そして、第１山谷関数ｆ1 (t) による第１移動ベクトルＸt と、第２山谷関数ｆ2 (t) による第２移動ベクトルＹt との和を対象辺Ｓ全体について取得すれば、第１および第２曲線要素Ｃ1 ，Ｃ2 の合成が取得され、これが対象辺Ｓに対応する最終曲線要素ＣFNL となる。この最終曲線要素ＣFNL は、対象辺Ｓの両端点において各頂点法線ベクトルＮ1 ，Ｎ2 と直交する。図１１は、変数ｔの同じ値に関する第１移動ベクトルＸt と第２移動ベクトルＹt とのベクトル和が、対象辺Ｓ上の、変数ｔに対応する任意点Ｐt を始点として最終曲線要素ＣFNL 上に終点を有する移動ベクトルＺt を意味することを示している。図には、変数ｔがｔ1 ，ｔ2 ，ｔ3 であるときの３つの移動ベクトルＺt1，Ｚt2，Ｚt3が示されている。
【００２６】
ここで、値ｈの設定方法について説明する。
値ｈは、対象辺Ｓに対応する最終曲線要素ＣFNL がその対象辺Ｓの両端点Ｑ1 ，Ｑ2 において各頂点法線ベクトルＮ1 ，Ｎ2 と直交することとなるように設定される。
【００２７】
対象辺Ｓ上の任意点Ｐt の位置ベクトルをＰ(t) とすれば、第１曲線要素Ｃ1 上の任意点Ｒ1tであって対象辺Ｓ上の任意点Ｐt に対応するものの位置ベクトルＲ1 (t) は、
Ｒ1 (t) ＝Ｐ(t) ＋∫Ｎ1 ・ｆ1(t) dt
で表される。一方、第２曲線要素Ｃ2 上の任意点Ｒ2tであって対象辺Ｓ上の任意点Ｐt に対応するものの位置ベクトルＲ2 (L-t) は、
Ｒ2(L-t)＝Ｐ(L-t) ＋∫Ｎ2 ・ｆ2(L-t) dt
で表される。よって、最終曲線要素ＣFNL の第１端点Ｑ1 における位置ベクトルＲ(0) は、
Ｒ1(0)＋Ｒ2 (L)
＝｛Ｐ(0) ＋∫Ｎ1 ・ｆ1(t) dt ｝＋｛Ｐ(L) ＋∫Ｎ2 ・ｆ2(L-t) dt ｝
＝Ｐ(0) ＋Ｎ1 ・ｈ1 ＋Ｐ(L) ＋０
となる。ここで、第１端点Ｑ1 を始点、第２端点Ｑ2 を終点とするベクトルをＵと定義すれば、位置ベクトルＲ(0) は、
Ｕ＋Ｎ1 ・ｈ1 
となる。この位置ベクトルＲ(0) が０となるように、第１山谷関数ｆ1(t)の値ｈ1 が設定される。
同様にして、最終曲線要素ＣFNL の第２端点Ｑ2 における位置ベクトルＲ(L) は、
Ｒ1(L)＋Ｒ2 (0)
＝｛Ｐ(L) ＋∫Ｎ1 ・ｆ1(t) dt ｝＋｛Ｐ(0) ＋∫Ｎ2 ・ｆ2(L-t) dt ｝
＝Ｐ(L) ＋０＋Ｐ(0) ＋Ｎ2 ・ｈ2 
となる。この位置ベクトルＲ(L) は結局、
Ｕ＋Ｎ2 ・ｈ2 
となる。この位置ベクトルＲ(L) が０となるように、第２山谷関数ｆ2(t)の値ｈ2 が設定される。
【００２８】
次に、図７のＳ３２において、最終曲線要素ＣFNL （以下、単に「曲線要素Ｃ」という）上において、対象辺Ｓの中点ＰM （ｔ＝Ｌ／２）に対応する点ＲM が取得される。その対応点ＲM と中点ＰM との間の移動ベクトルＺM は、上述の説明から明らかなように、
ＺM ＝∫Ｎ1 ・ｆ1(L/2) dt ＋∫Ｎ2 ・ｆ2(L/2) dt
で表される。図１２には、その移動ベクトルＺM の一例が示されている。
【００２９】
続いて、図７のＳ３３において、複数の元の三角形が順に対象三角形とされるとともに、対象三角形が４つの三角形に細分化される。対象三角形の３つの頂点と上記Ｓ３２において取得された３つの対応点ＲM とからなる６つの点を相互に複数の直線要素でつなぐことによって複数の三角形に分割されるのである。図１３には、３つの頂点Ｑ1 ，Ｑ2 ，Ｑ3 を有する元の三角形１７０が示されるとともに、その元の三角形１７０が、３つの頂点Ｑ1 ，Ｑ2 ，Ｑ3 と３つの対応点ＲM1，ＲM2，ＲM3とからなる６つの点を複数の直線要素に互いにつなぐことにより、４つの新たな三角形１７２，１７４，１７６，１７８に分割される様子が示されている。なお、図１３以後の各図において、「Ｃ1 」，「Ｃ2 」，「Ｃ3 」はそれぞれ、辺Ｓ1 ，Ｓ2 ，Ｓ3 に対応する最終曲線要素を示す。
【００３０】
その後、Ｓ３４において、上記Ｓ３２において取得された複数の対応点、すなわち、細分化のために発生させられた新規頂点における頂点法線ベクトルが決定される。その頂点法線ベクトルは、元の三角形の３辺のうち、その新規頂点が位置する辺の両端点における既知の２つの頂点法線ベクトルを平均化して正規化する（ベクトルの長さを１とする）ことにより、決定される。図１４に例示するように、新規頂点ＲM1Ｚ1 については、それの対応する辺Ｓ1 の両端点Ｑ1 ，Ｑ2 における頂点法線ベクトルＮ1 ，Ｎ2 を平均化して正規化したベクトル、すなわち、
（Ｎ1 ＋Ｎ2 ）／｜Ｎ1 ＋Ｎ2 ｜
が取得される。他の新規頂点ＲM2，ＲM3についても同様である。
【００３１】
続いて、図７のＳ３５において、三角形の細分化を終了させるべきであるか否かが判定される。具体的には、元の三角形の各辺とそれに対応する曲線要素との隔たりとして、元の三角形の各辺の中点ＰM （ｔ＝Ｌ／２）に対応する前記移動ベクトルＺM の大きさ（以下、「移動量Ｍ」という）が用いられるとともに、元の三角形の３辺全てについて、その移動量Ｍが、作業者により指定された誤差以下であるか否かが判定される。図１５には、辺Ｓ1 と曲線要素Ｃ1 との隔たりとして移動量Ｍ1 、辺Ｓ2 と曲線要素Ｃ2 との隔たりとして移動量Ｍ2 、辺Ｓ3 と曲線要素Ｃ3 との隔たりとして移動量Ｍ3 が用いられる様子が示されている。
【００３２】
元の三角形の３辺全てについて、移動量Ｍが指定誤差以下である場合には、細分化を終了させるべきであると判定される。これに対して、少なくとも一つの辺についての移動量Ｍが指定誤差より大きい場合には、細分化を終了させるべきでないと判定される。この場合には、その後、Ｓ３６において、細分化された各三角形が次回に細分化すべき元の三角形に選ばれ、その後、Ｓ３１〜Ｓ３５が前記の場合と同様にして実行される。
【００３３】
以上のようにしてスムース化プログラムの一回の実行が終了すれば、図１３および図１４に示す元の三角形１７０は、図１６に示すように、複数の三角形に細分化されることになる。
【００３４】
次に、本発明の第２実施形態を説明する。ただし、本実施形態は、先の第１実施形態と対象三角形を分割する点について異なり、他の点については共通であるため、異なる点についてのみ詳細に説明し、共通の点については同一の符号を使用することによって詳細な説明を省略する。
【００３５】
第１実施形態においては、元の三角形の各辺とそれに対応する曲線要素との隔たりが大きいか否かを問わず、全ての辺に対応する全ての曲線要素が２分割されてその分割点が新規頂点として発生させられるようになっている。なお、曲線要素を２分割することと各辺を２分割することとは厳密には一致しないが、曲線要素が各辺に関連付けて発生させられるものであることに着目するとともに、元の三角形の各辺との関係を重視するため、以下、曲線要素の２分割を各辺の２分割ともいう。そして、本実施形態においては、隔たりが大きい辺に限り、２分割が行われるようになっている。
【００３６】
図１７には、本実施形態における三角形細分化ルーチンがフローチャートで表されている。以下、本ルーチンを説明するが、図７のルーチンと共通するステップについては簡単に説明する。
【００３７】
まず、Ｓ５１において、第１実施形態におけると同様にして山谷関数ｆ(t) が定義される。次に、Ｓ５２において、対象辺Ｓの中点ＰM に対応する移動量Ｍが取得される。この取得は、第１実施形態におけると同様にして行われる。その後、Ｓ５３において、対象三角形の３辺全てにつき、取得された移動量Ｍが指定誤差（基準値）より大きいか否かが判定される。
【００３８】
３辺全てについて移動量Ｍが指定誤差より大きい場合には、判定がＹＥＳとなり、Ｓ５４において、それら３辺がそれぞれ２分割され、それにより、３辺全てについて３つの新規頂点が発生させられる。その後、Ｓ５５において、その発生させられた３つの新規頂点と対象三角形の３つの頂点とからなる６つの点を複数の直線要素でつなぐことによって対象三角形が細分化される。その一例が図１８の(a) に示されている。
【００３９】
これに対して、２辺についてのみ移動量Ｍが指定誤差より大きい場合には、Ｓ５３の判定はＮＯ、Ｓ５６の判定はＹＥＳとなり、Ｓ５７において、その２辺がそれぞれ２分割され、それにより、その２辺について２つの新規頂点が発生させられる。その後、Ｓ５６において、その発生させられた２つの新規頂点と対象三角形の３つの頂点とからなる５つの点を複数の直線要素でつなぐことによって対象三角形が細分化される。
【００４０】
５つの点を複数の直線要素でつなぐ方法には２つ存在する。５つの点を１本の閉じた折れ線でつなぐと、１つの五角形が発生し、その五角形を１本の直線要素で分割すると、１つの三角形と１つの四角形とが発生する。その四角形を１本の直線要素で２つの三角形に分割する際に、その分割線に四角形の２本の対角線のいずれを選ぶかによって２つの方法が存在するのである。本実施形態においては、２本の対角線のうち、その四角形の４つの頂点のうち角度が最大であるものを通過する対角線が分割線に選ばれるようになっていて、四角形の分割によって鈍角三角形ができる限り発生しないようになっている。図１８の(b) には、その一例が示されている。
【００４１】
また、対象三角形の１辺についてのみ移動量Ｍが指定誤差より大きい場合には、Ｓ５３およびＳ５６の判定は共にＮＯとなり、Ｓ５９の判定はＹＥＳとなる。その後、Ｓ６０において、その１辺が２分割され、それにより、１つの新規頂点が発生させられる。続いて、Ｓ６１において、その発生させられた１つの新規頂点と対象三角形の３つの頂点とからなる４つの点を複数の直線要素でつなぐことにより、対象三角形が分割される。図１８の(c) には、その一例が示されている。
【００４２】
いずれの場合にも、その後、Ｓ６２において、細分化された各三角形（細分化により発生した新たな三角形）が次回にも細分化させるべき三角形に選ばれ、続いて、Ｓ５１に戻り、新たな対象三角形について前記の場合と同様な処理が行われる。
【００４３】
以上、対象三角形の３辺のいずれかの移動量Ｍが指定誤差より大きい場合を説明したが、いずれの辺の移動量Ｍも指定誤差以下である場合には、Ｓ５３とＳ５６とＳ５９との判定がいずれもＮＯとなり、新規頂点の発生も対象三角形の細分化も行われることなく、本ルーチンの一回の実行が終了する。
【００４４】
次に、本発明の第３実施形態を説明する。ただし、本実施形態は、先の第１および第２実施形態と共通する点が多いため、異なる点についてのみ詳細に説明する。
【００４５】
先の第２実施形態については、作業者がコンピュータ１０に対して近似ポリゴン表面スムース化の実行指令を出したならば、自動的に曲面全体が細分化領域となって、実行対象である複数の元の三角形の全てが細分化の対象となる。これに対して、本実施形態においては、曲面のうち作業者がその細分化を行いたい領域を指定可能となっている。
【００４６】
図１９には、本実施形態における近似ポリゴン表面スムース化プログラムがフローチャートで表されている。以下、本プログラムを説明するが、最先の第１実施形態における近似ポリゴン表面スムース化プログラムと共通するステップと、直前の第２実施形態における三角形細分化ルーチンと共通するステップとが存在するため、それら共通するステップについては簡単に説明する。
【００４７】
まず、Ｓ７１において、作業者が入力装置１２を操作することにより、複数の元の三角形に対して、細分化すべき領域を指定することが行われたか否かが判定される。今回は行われていないと仮定すれば、判定がＮＯとなり、本プログラムの一回の実行が終了するが、行われたと仮定すれば、判定がＹＥＳとなり、Ｓ７２に移行する。
【００４８】
図２０の(a) には、細分化領域を指定する様子が示されている。作業者は、表示装置１６の画面に表示されている図形の一部を閉じた線２００（折れ線または曲線）で囲むことにより、細分化領域を指定する。
【００４９】
Ｓ７２においては、複数の元の三角形のうち細分化領域内に存在するものが抽出される。図２０の(b) には、細分化領域内に存在するものとして抽出された複数の元の三角形が示されている。その後、Ｓ７３〜Ｓ７５において、第１実施形態におけると同様にして、隣接関係規定データの付加，特徴線の抽出および頂点法線ベクトルの決定が行われる。続いて、Ｓ７６において、第２実施形態におけると同様にして、三角形細分化が行われる。図２０の(c) には、細分化領域内の複数の元の三角形が細分化される様子が拡大して示されている。以上で本プログラムの一回の実行が終了する。
【００５０】
なお、図２０に示す例のように、閉じた線２００で囲まれた領域内に閉じた特徴線２０２で存在する場合には、閉じた線２００で囲まれた領域全体を細分化領域として定義したり、閉じた線２００と特徴線２０２とで囲まれた領域を細分化領域として定義することができる。
【００５１】
以上、本発明のいくつかの実施形態を図面に基づいて詳細に説明したが、これらの他にも、特許請求の範囲を逸脱することなく、当業者の知識に基づいて種々の変形，改良を施した形態で本発明を実施することができる。
【図面の簡単な説明】
【図１】本発明の第１実施形態である近似ポリゴン曲面スムース化方法を実施するためのデータ処理システムを示すブロック図である。
【図２】図１の記録媒体に記録されている近似ポリゴン曲面スムース化プログラムを示すフローチャートである。
【図３】図２のＳ１を説明するための斜視図である。
【図４】図２のＳ２を説明するための斜視図である。
【図５】図２のＳ３の詳細を頂点法線ベクトル決定ルーチンとして示すフローチャートである。
【図６】その頂点法線ベクトル決定ルーチンを説明するための斜視図である。
【図７】図２のＳ４の詳細を三角形細分化ルーチンとして示すフローチャートである。
【図８】図７のＳ３１における山谷関数を示すグラフである。
【図９】そのＳ３１における移動ベクトルを説明するための斜視図である。
【図１０】上記山谷関数を２つ重ね合わせることによって曲線要素を取得する様子を示す斜視図である。
【図１１】上記Ｓ３１における移動ベクトルを説明するための斜視図である。
【図１２】図７のＳ３２を説明するための斜視図である。
【図１３】図７のＳ３３を説明するための斜視図である。
【図１４】図７のＳ３４を説明するための斜視図である。
【図１５】図７のＳ３５を説明するための斜視図である。
【図１６】上記近似ポリゴン表面スムース化プログラムの一実行結果を示す斜視図である。
【図１７】本発明の第２実施形態である近似ポリゴン表面スムース化方法において使用される三角形細分化ルーチンを示すフローチャートである。
【図１８】その三角形細分化ルーチンを説明するための斜視図である。
【図１９】本発明の第３実施形態である近似ポリゴン表面スムース化方法において使用される近似ポリゴン表面スムース化ルーチンを示すフローチャートである。
【図２０】その近似ポリゴン表面スムース化ルーチンを説明するための斜視図である。
【符号の説明】
１０：コンピュータ
２４：記録媒体
１００，１０６：辺
１０２，１０４，１０８，１１０，１２２，１２４，１２６，１２８，１３０，１５４，１５６，１５８，１６０，１６２，１７０：元の三角形
１２０，１５２：対象頂点
１３２，１３４，１３６，１３８，１４０：面法線ベクトル
１４２：頂点法線ベクトル
１５０：特徴線
１６４：第１頂点法線ベクトル
１６６：第２頂点法線ベクトル
１７２，１７４，１７６，１７８：新たな三角形
Ｎ1 ，Ｎ2 ，Ｎ3 ：頂点法線ベクトル
Ｃ1 ，Ｃ2 ，Ｃ3 ：曲線要素
Ｓ1 ，Ｓ2 ，Ｓ3 ：辺
Ｑ1 ，Ｑ2 ，Ｑ3 ：端点
ＲM1，ＲM2，ＲM3：対応点
ＰM ：中点
Ｍ1 ，Ｍ2 ，Ｍ3 ：移動量
Ｚt1，Ｚt2，Ｚt3：移動ベクトル
Ｐt ：辺Ｓ上の任意点
Ｒt ：曲線要素Ｃ上の任意点
【図１】
0003643237.tif 000002
【図２】
0003643237.tif 000003
【図３】
0003643237.tif 000004
【図４】
0003643237.tif 000005
【図５】
0003643237.tif 000006
【図６】
0003643237.tif 000007
【図７】
0003643237.tif 000008
【図８】
0003643237.tif 000009
【図９】
0003643237.tif 000010
【図１０】
0003643237.tif 000011
【図１１】
0003643237.tif 000012
【図１２】
0003643237.tif 000013
【図１３】
0003643237.tif 000014
【図１４】
0003643237.tif 000015
【図１５】
0003643237.tif 000016
【図１６】
0003643237.tif 000017
【図１７】
0003643237.tif 000018
【図１８】
0003643237.tif 000019
【図１９】
0003643237.tif 000020
【図２０】
0003643237.tif 000021