(57)【特許請求の範囲】
【請求項１】
多角形又は多面体である複数の要素を組み合わせた二次元又は三次元のメッシュが所定の図形の形状を表現しているか否かを、演算部及び記憶部を備えるコンピュータによって判定するメッシュ形状判定方法において、
所定の図形の形状を表現した形状モデルの表面に、メッシュ上の複数の節点のうち前記図形の表面に相当する位置の節点に対応する点を演算部で設けて記憶部に記憶し、
前記形状モデルの表面を、該表面に設けた点を互いに結んで形成される複数の線又は平面に演算部で分割し、分割した複数の線又は平面を集めた形状境界集合を記憶部に記憶し、
前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶部に記憶し、
前記形状境界集合と前記メッシュ境界集合とを演算部で比較して、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合に、前記メッシュは前記図形の形状を表現していると演算部で判定すること
を特徴とするメッシュ形状判定方法。
【請求項２】
二次元又は三次元の図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを、演算部及び記憶部を備えるコンピュータによって生成するメッシュ生成方法において、
前記図形の形状を表現した形状モデルの表面上に、頂点を含む複数の点を演算部で設けて記憶部に記憶し、
前記形状モデルの表面上に設けた点に対応する点を含む複数の点を演算部で定義して記憶部に記憶し、
定義した点を節点とするメッシュを演算部で生成して記憶部に記憶し、
請求項１に記載のメッシュ形状判定方法を用いて、生成したメッシュの形状を演算部で判定して判定結果を記憶部に記憶し、
前記メッシュは前記図形の形状を表現していないと判定された場合は、前記形状境界集合に含まれる線又は平面のうち、前記メッシュ境界集合に含まれる線又は平面に対応していない線又は平面を演算部で抽出して記憶部に記憶し、
前記形状モデルの抽出した線又は平面上に点を演算部で付加して記憶部に記憶し、
付加した点に対応する点を演算部で前記メッシュ内に定義して記憶部に記憶し、
定義した点を追加の節点として新たなメッシュを演算部で生成して記憶部に記憶すること
を特徴とするメッシュ生成方法。
【請求項３】
前記メッシュは前記図形の形状を表現していると判定された場合は、前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を演算部で選択して記憶部に記憶し、
選択した要素に隣り合う要素を順に演算部で選択し、選択した要素と直前に選択していた要素との間の境界が、前記形状境界集合に含まれる線又は平面のいずれにも対応しない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると演算部で判定して判定結果を記憶部に記憶し、
選択した要素と直前に選択していた要素との間の境界が、前記形状境界集合に含まれる線又は平面のいずれかに対応する場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると演算部で判定して判定結果を記憶部に記憶し、
直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると演算部で判定して判定結果を記憶部に記憶し、
前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を演算部で削除して、前記要素を削除したメッシュを記憶部に記憶すること
を特徴とする請求項２に記載のメッシュ生成方法。
【請求項４】
デラウニ法を用いてメッシュを演算部で生成することを特徴とする請求項２又は３に記載のメッシュ生成方法。
【請求項５】
二次元又は三次元の図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを生成するメッシュ生成装置において、
所定の図形の形状を表現した形状モデルを受け付ける手段と、
該形状モデルの表面上に、頂点を含む複数の点を設ける手段と、
前記形状モデルの表面上に設けた点の夫々に対応する点を含む複数の点を、前記形状モデルとは別に定義する手段と、
定義した複数の点を節点としたメッシュを生成する手段と、
前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割する手段と、
分割した複数の線又は平面を集めた形状境界集合を記憶する手段と、
前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶する手段と、
前記形状境界集合及び前記メッシュ境界集合を比較する手段と、
前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応しない場合は、対応しない線又は平面を抽出する手段と、
前記形状モデルの表面上の、抽出した線又は平面上に点を付加する手段と、
前記形状モデルの表面上に付加した点に対応する点を前記メッシュ内に定義する手段と、
定義された点を追加の節点として新たなメッシュを生成する手段と、
前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュ境界集合に含まれる線又は平面のうち、前記形状境界集合に含まれる複数の線又は平面に対応する線又は平面に関連付けて、形状の境界を示すフラグを記憶する手段と、
前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を選択する手段と、
選択した要素に隣り合う要素を順に選択していく手段と、
選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられていない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると判定する手段と、
選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられている場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると判定し、直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると判定する手段と、前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を削除する手段とを備えることを特徴とするメッシュ生成装置。
【請求項６】
コンピュータに、多角形又は多面体である複数の要素を組み合わせた二次元又は三次元のメッシュが所定の図形の形状を表現しているか否かを判定させるコンピュータプログラムにおいて、
コンピュータに、所定の図形の形状を表現した形状モデルの表面に、メッシュ上の複数の節点のうち前記図形の表面に相当する位置の節点に対応する点を設けさせる手順と、
コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、
コンピュータに、分割した複数の線又は平面の情報を集めた形状境界集合を記憶させる手順と、
コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、
コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、
コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュは前記図形の形状を表現していると判定させる手順とを含むことを特徴とするコンピュータプログラム。
【請求項７】
コンピュータに、二次元又は三次元の図形の形状を表現した形状モデルを用いて、前記図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを生成させるコンピュータプログラムにおいて、
コンピュータに、前記形状モデルの表面上に、頂点を含む複数の点を設けさせる手順と、
コンピュータに、前記形状モデルの表面上に設けた点の夫々に対応する点を含む複数の点を、前記形状モデルとは別に定義させる手順と、
コンピュータに、定義した複数の点を節点としたメッシュを生成させる手順と、
コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、
コンピュータに、分割した複数の線又は平面を集めた形状境界集合を記憶させる手順と、
コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、
コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、
コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応しない場合は、対応しない線又は平面を抽出させる手順と、
コンピュータに、前記形状モデルの表面上の、抽出した線又は平面上に点を付加させる手順と、
前記形状モデルの表面上に付加した点に対応する点を前記メッシュ内に定義させる手順と、
コンピュータに、定義された点を追加の節点として新たなメッシュを生成させる手順と、
コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュ境界集合に含まれる線又は平面のうち、前記形状境界集合に含まれる複数の線又は平面に対応する線又は平面に関連付けて、形状の境界を示すフラグを記憶させる手順と、
コンピュータに、前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を選択させる手順と、
コンピュータに、選択した要素に隣り合う要素を順に選択させていく手順と、コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられていない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると判定させる手順と、
コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられている場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると判定させ、直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると判定させる手順と、
コンピュータに、前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を削除させる手順とを含むことを特徴とするコンピュータプログラム。
【請求項８】
コンピュータに、多角形又は多面体である複数の要素を組み合わせた二次元又は三次元のメッシュが所定の図形の形状を表現しているか否かを判定させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、
コンピュータに、所定の図形の形状を表現した形状モデルの表面に、メッシュ上の複数の節点のうち前記図形の表面に相当する位置の節点に対応する点を設けさせる手順と、
コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、
コンピュータに、分割した複数の線又は平面の情報を集めた形状境界集合を記憶させる手順と、
コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、
コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、
コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュは前記図形の形状を表現していると判定させる手順とを含むコンピュータプログラムを記録してあることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【請求項９】
コンピュータに、二次元又は三次元の図形の形状を表現した形状モデルを用いて、前記図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、
コンピュータに、前記形状モデルの表面上に、頂点を含む複数の点を設けさせる手順と、
コンピュータに、前記形状モデルの表面上に設けた点の夫々に対応する点を含む複数の点を、前記形状モデルとは別に定義させる手順と、
コンピュータに、定義した複数の点を節点としたメッシュを生成させる手順と、
コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、
コンピュータに、分割した複数の線又は平面を集めた形状境界集合を記憶させる手順と、
コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、
コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、
コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応しない場合は、対応しない線又は平面を抽出させる手順と、
コンピュータに、前記形状モデルの表面上の、抽出した線又は平面上に点を付加させる手順と、
前記形状モデルの表面上に付加した点に対応する点を前記メッシュ内に定義させる手順と、
コンピュータに、定義された点を追加の節点として新たなメッシュを生成させる手順と、
コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュ境界集合に含まれる線又は平面のうち、前記形状境界集合に含まれる複数の線又は平面に対応する線又は平面に関連付けて、形状の境界を示すフラグを記憶させる手順と、
コンピュータに、前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を選択させる手順と、
コンピュータに、選択した要素に隣り合う要素を順に選択させていく手順と、コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられていない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると判定させる手順と、
コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられている場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると判定させ、直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると判定させる手順と、
コンピュータに、前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を削除させる手順とを含むコンピュータプログラムを記録してあることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、生成した二次元または三次元のメッシュが図形を表現しているか否かを判定するメッシュ形状判定方法、該メッシュ形状判定方法を用いたメッシュ生成方法、該メッシュ生成方法を実現するためのメッシュ生成装置、前記メッシュ形状判定方法および前記メッシュ生成方法をコンピュータを用いて実現するためのコンピュータプログラム、及び該コンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体に関する。
【０００２】
【従来の技術】
従来、コンピュータを用いて二次元又は三次元の図形を形成し、構造物の設計または構造解析などに用いることが広く行われている。コンピュータを用いて形成された図形は、多角形、円または球などの基本的な図形を組み合わせることでより複雑な図形を表現しているのが通常である。このため、任意の点または図形などが他の図形に包含されているか否かを判定する包含判定の処理は、図形の形成または変形などの図形処理において重要な処理であり、頻繁に行われている処理である。
【０００３】
図９は、従来の包含判定の方法を示す模式図である。従来の第１の方法では、包含判定を行うべき点から任意の方向へ半直線を伸ばし、該半直線が図形と交わる交点数が偶数の場合は、前記点は前記図形の外部にあって包含されていないと判定し、前記半直線が図形と交わる交点数が奇数の場合は、前記点は前記図形の内部に包含されていると判定する。図９（ａ）に示した例では、図形ＡＢＣＤＥの外部にある点Ｐ１から伸ばされた半直線ｌ１は、図形ＡＢＣＤＥと２箇所で交わっており、交点数が偶数であることによって点Ｐ１が図形ＡＢＣＤＥに包含されないことが判定され、また、図形ＡＢＣＤＥの内部にある点Ｐ２から伸ばされた半直線ｌ２は、図形ＡＢＣＤＥと１箇所で交わっており、交点数が奇数であることによって点Ｐ２が図形ＡＢＣＤＥに包含されていることが判定される。図形が三次元である場合でも、同様に包含判定ができる。
【０００４】
従来の第２の方法では、包含判定を行うべき点と図形の各頂点とを線分で結び、隣り合う線分間の角度を合計して、角度の合計値が２πである場合には、前記点は前記図形の内部に包含されていると判定し、角度の合計値が２πより小さい場合には、前記点は前記図形の外部にあって包含されていないと判定する。図９（ｂ）に示した例では、図形ＡＢＣＤＥの内部にある点Ｐ２と図形ＡＢＣＤＥの各頂点とを結んだ線分間の角度は、合計して２πとなるため、点Ｐ２が図形ＡＢＣＤＥに包含されていることが判定され、また、図形ＡＢＣＤＥの外部にある点Ｐ５と図形ＡＢＣＤＥの各頂点とを結んだ線分間の角度は、合計して２πよりも小さいため、点Ｐ５が図形ＡＢＣＤＥに包含されないことが判定される。図形が三次元の場合は、通常の図形は多角形を三次元的に組み合わせることで構成されている。各多角形と包含判定を行うべき点との間の立体角を合計し、立体角の合計値が４πである場合には、前記点は前記図形の内部に包含されていると判定し、立体角の合計値が４πより小さい場合には、前記点は前記図形の外部にあって包含されていないと判定する。
【０００５】
二次元または三次元の複雑な図形を、簡単な形状の多角形または多面体を複数組み合わせたメッシュで表現し、物体の構造解析のシミュレーション等に利用することが従来より行われている。図形を表現するメッシュを生成するために、デラウニ法などの自動でメッシュを生成する方法が用いられている。自動でメッシュを生成する方法では、図形の頂点を初めとする各所の点を結んで複数の多角形及び多面体を生成するため、各所の点を生成する方法または点同士を結ぶ方法によっては、生成されたメッシュが図形の形状を表現していない場合がある。このため、生成されたメッシュを構成する多角形または多面体である複数の要素の夫々について、前述の方法を用い、要素内部の点が図形に包含されているか否かの包含判定を行うことで、要素を組み合わせたメッシュが図形の形状を表現しているか否かを判定する形状判定を行い、メッシュが図形の形を表現していない場合は、点を増やして更にメッシュ生成を行い、前記領域のメッシュが図形の形を表現するまで処理を繰り返して、図形を表現するメッシュを生成する。
【０００６】
【発明が解決しようとする課題】
前述の第１の包含判定の方法では、包含判定を行うべき点から伸ばした半直線が、図形に交わるのではなく接する場合がある。図９（ａ）に示した例では、点Ｐ３から伸ばした半直線ｌ３は図形の頂点Ｂに接しており、点Ｐ４から伸ばした半直線ｌ４は図形の頂点Ｃに接している。これらのごとく半直線が図形に接している接点は、交点として数えない又は２つの交点として数える等の処理を行う必要がある。コンピュータを用いた計算で接点と交点とを区別するためには、接点または交点の前後で図形の表面が極値をとっているか否かを判定する等の計算が必要となり、包含判定に時間がかかるという問題があった。また、点と図形とが接点または交点の判定が困難な位置関係をとる場合があり、包含判定が不確実であるという問題があった。
【０００７】
前述の第２の包含判定の方法では、角度または立体角を求めて、求めた角度または立体角を合計する計算を行うため、包含判定に時間がかかるという問題があった。また、コンピュータによる計算の誤差が蓄積するため、図形外にある筈の点についての角度または立体角の合計が２π又は４πを超えてしまう等、包含判定に失敗する場合があり、包含判定が不確実であるという問題があった。
【０００８】
二次元または三次元の図形を表現するメッシュを生成する場合、生成したメッシュが図形の形状を表現しているか否かを判定する形状判定を行うときに、前述の包含判定の方法を用いているために、形状判定に時間がかかり、また形状判定が不確実であるという問題がある。
【０００９】
本発明は、斯かる事情に鑑みてなされたものであって、その目的とするところは、図形の表面を構成する辺または平面の情報を記憶しておき、生成したメッシュを構成する夫々の要素の境界線または境界面と比較して、境界線又は境界面の中に図形の表面を構成する線または平面が含まれている場合に、生成したメッシュが図形の形状を表現していると判定することにより、短時間で確実に形状判定を行うことができるメッシュ形状判定方法、該メッシュ形状判定方法を用いたメッシュ生成方法、該メッシュ生成方法を実現するためのメッシュ生成装置、前記メッシュ形状判定方法および前記メッシュ生成方法をコンピュータを用いて実現するためのコンピュータプログラム、及び該コンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体を提供することにある。
【００１０】
【課題を解決するための手段】
第１発明に係るメッシュ形状判定方法は、多角形又は多面体である複数の要素を組み合わせた二次元又は三次元のメッシュが所定の図形の形状を表現しているか否かを、演算部及び記憶部を備えるコンピュータによって判定するメッシュ形状判定方法において、所定の図形の形状を表現した形状モデルの表面に、メッシュ上の複数の節点のうち前記図形の表面に相当する位置の節点に対応する点を演算部で設けて記憶部に記憶し、前記形状モデルの表面を、該表面に設けた点を互いに結んで形成される複数の線又は平面に演算部で分割し、分割した複数の線又は平面を集めた形状境界集合を記憶部に記憶し、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶部に記憶し、前記形状境界集合と前記メッシュ境界集合とを演算部で比較して、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合に、前記メッシュは前記図形の形状を表現していると演算部で判定することを特徴とする。
【００１１】
第２発明に係るメッシュ生成方法は、二次元又は三次元の図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを、演算部及び記憶部を備えるコンピュータによって生成するメッシュ生成方法において、前記図形の形状を表現した形状モデルの表面上に、頂点を含む複数の点を演算部で設けて記憶部に記憶し、前記形状モデルの表面上に設けた点に対応する点を含む複数の点を演算部で定義して記憶部に記憶し、定義した点を節点とするメッシュを演算部で生成して記憶部に記憶し、第１発明に係るメッシュ形状判定方法を用いて、生成したメッシュの形状を演算部で判定して判定結果を記憶部に記憶し、前記メッシュは前記図形の形状を表現していないと判定された場合は、前記形状境界集合に含まれる線又は平面のうち、前記メッシュ境界集合に含まれる線又は平面に対応していない線又は平面を演算部で抽出して記憶部に記憶し、前記形状モデルの抽出した線又は平面上に点を演算部で付加して記憶部に記憶し、付加した点に対応する点を演算部で前記メッシュ内に定義して記憶部に記憶し、定義した点を追加の節点として新たなメッシュを演算部で生成して記憶部に記憶することを特徴とする。
【００１２】
第３発明に係るメッシュ生成方法は、前記メッシュは前記図形の形状を表現していると判定された場合は、前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を演算部で選択して記憶部に記憶し、選択した要素に隣り合う要素を順に演算部で選択し、選択した要素と直前に選択していた要素との間の境界が、前記形状境界集合に含まれる線又は平面のいずれにも対応しない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると演算部で判定して判定結果を記憶部に記憶し、選択した要素と直前に選択していた要素との間の境界が、前記形状境界集合に含まれる線又は平面のいずれかに対応する場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると演算部で判定して判定結果を記憶部に記憶し、直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると演算部で判定して判定結果を記憶部に記憶し、前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を演算部で削除して、前記要素を削除したメッシュを記憶部に記憶することを特徴とする。
【００１３】
第４発明に係るメッシュ生成方法は、デラウニ法を用いてメッシュを演算部で生成することを特徴とする。
【００１４】
第５発明に係るメッシュ生成装置は、二次元又は三次元の図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを生成するメッシュ生成装置において、所定の図形の形状を表現した形状モデルを受け付ける手段と、該形状モデルの表面上に、頂点を含む複数の点を設ける手段と、前記形状モデルの表面上に設けた点の夫々に対応する点を含む複数の点を、前記形状モデルとは別に定義する手段と、定義した複数の点を節点としたメッシュを生成する手段と、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割する手段と、分割した複数の線又は平面を集めた形状境界集合を記憶する手段と、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶する手段と、前記形状境界集合及び前記メッシュ境界集合を比較する手段と、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応しない場合は、対応しない線又は平面を抽出する手段と、前記形状モデルの表面上の、抽出した線又は平面上に点を付加する手段と、前記形状モデルの表面上に付加した点に対応する点を前記メッシュ内に定義する手段と、定義された点を追加の節点として新たなメッシュを生成する手段と、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュ境界集合に含まれる線又は平面のうち、前記形状境界集合に含まれる複数の線又は平面に対応する線又は平面に関連付けて、形状の境界を示すフラグを記憶する手段と、前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を選択する手段と、選択した要素に隣り合う要素を順に選択していく手段と、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられていない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると判定する手段と、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられている場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると判定し、直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると判定する手段と、前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を削除する手段とを備えることを特徴とする。
【００１５】
第６発明に係るコンピュータプログラムは、コンピュータに、多角形又は多面体である複数の要素を組み合わせた二次元又は三次元のメッシュが所定の図形の形状を表現しているか否かを判定させるコンピュータプログラムにおいて、コンピュータに、所定の図形の形状を表現した形状モデルの表面に、メッシュ上の複数の節点のうち前記図形の表面に相当する位置の節点に対応する点を設けさせる手順と、コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、コンピュータに、分割した複数の線又は平面の情報を集めた形状境界集合を記憶させる手順と、コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュは前記図形の形状を表現していると判定させる手順とを含むことを特徴とする。
【００１６】
第７発明に係るコンピュータプログラムは、コンピュータに、二次元又は三次元の図形の形状を表現した形状モデルを用いて、前記図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを生成させるコンピュータプログラムにおいて、コンピュータに、前記形状モデルの表面上に、頂点を含む複数の点を設けさせる手順と、コンピュータに、前記形状モデルの表面上に設けた点の夫々に対応する点を含む複数の点を、前記形状モデルとは別に定義させる手順と、コンピュータに、定義した複数の点を節点としたメッシュを生成させる手順と、コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、コンピュータに、分割した複数の線又は平面を集めた形状境界集合を記憶させる手順と、コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応しない場合は、対応しない線又は平面を抽出させる手順と、コンピュータに、前記形状モデルの表面上の、抽出した線又は平面上に点を付加させる手順と、前記形状モデルの表面上に付加した点に対応する点を前記メッシュ内に定義させる手順と、コンピュータに、定義された点を追加の節点として新たなメッシュを生成させる手順と、コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュ境界集合に含まれる線又は平面のうち、前記形状境界集合に含まれる複数の線又は平面に対応する線又は平面に関連付けて、形状の境界を示すフラグを記憶させる手順と、コンピュータに、前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を選択させる手順と、コンピュータに、選択した要素に隣り合う要素を順に選択させていく手順と、コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられていない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると判定させる手順と、コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられている場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると判定させ、直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると判定させる手順と、コンピュータに、前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を削除させる手順とを含むことを特徴とする。
【００１７】
第８発明に係るコンピュータでの読み取りが可能な記録媒体は、コンピュータに、多角形又は多面体である複数の要素を組み合わせた二次元又は三次元のメッシュが所定の図形の形状を表現しているか否かを判定させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、所定の図形の形状を表現した形状モデルの表面に、メッシュ上の複数の節点のうち前記図形の表面に相当する位置の節点に対応する点を設けさせる手順と、コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、コンピュータに、分割した複数の線又は平面の情報を集めた形状境界集合を記憶させる手順と、コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュは前記図形の形状を表現していると判定させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【００１８】
第９発明に係るコンピュータでの読み取りが可能な記録媒体は、コンピュータに、二次元又は三次元の図形の形状を表現した形状モデルを用いて、前記図形を多角形又は多面体である複数の要素の組み合わせで表現した二次元又は三次元のメッシュを生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、前記形状モデルの表面上に、頂点を含む複数の点を設けさせる手順と、コンピュータに、前記形状モデルの表面上に設けた点の夫々に対応する点を含む複数の点を、前記形状モデルとは別に定義させる手順と、コンピュータに、定義した複数の点を節点としたメッシュを生成させる手順と、コンピュータに、前記形状モデルの表面を、表面上に設けた点を互いに結んで形成される複数の線又は平面に分割させる手順と、コンピュータに、分割した複数の線又は平面を集めた形状境界集合を記憶させる手順と、コンピュータに、前記メッシュの各要素間の境界である複数の線又は平面を集めたメッシュ境界集合を記憶させる手順と、コンピュータに、前記形状境界集合及び前記メッシュ境界集合を比較させる手順と、コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応しない場合は、対応しない線又は平面を抽出させる手順と、コンピュータに、前記形状モデルの表面上の、抽出した線又は平面上に点を付加させる手順と、前記形状モデルの表面上に付加した点に対応する点を前記メッシュ内に定義させる手順と、コンピュータに、定義された点を追加の節点として新たなメッシュを生成させる手順と、コンピュータに、前記形状境界集合に含まれる複数の線又は平面の夫々が、前記メッシュ境界集合に含まれる線又は平面のいずれかに対応する場合は、前記メッシュ境界集合に含まれる線又は平面のうち、前記形状境界集合に含まれる複数の線又は平面に対応する線又は平面に関連付けて、形状の境界を示すフラグを記憶させる手順と、コンピュータに、前記メッシュを構成する複数の要素から、前記図形外又は前記図形内に対応する領域に属する一の要素を選択させる手順と、コンピュータに、選択した要素に隣り合う要素を順に選択させていく手順と、コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられていない場合は、選択した要素は、直前に選択していた要素と同じ領域に属していると判定させる手順と、コンピュータに、選択した要素と直前に選択していた要素との間の境界に、前記フラグが関係付けられている場合は、直前に選択していた要素が前記図形外に対応する領域に属しているときには、選択した要素は前記図形内に対応する領域に属していると判定させ、直前に選択していた要素が前記図形内に対応する領域に属しているときには、選択した要素は前記図形外に対応する領域に属していると判定させる手順と、コンピュータに、前記メッシュを構成する要素のうち、前記図形外に対応する領域に属していると判定された要素を削除させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【００１９】
第１、第６及び第８発明においては、二次元又は三次元の図形の形状を表現する形状モデルの表面を構成する複数の線又は平面を集めた形状境界集合を記憶しておき、生成したメッシュを構成する夫々の要素の境界である線又は平面のメッシュ境界集合と比較し、形状境界集合の中の線又は平面の夫々がメッシュ境界集合の中の線又は平面のいずれかに対応している場合は、メッシュが図形の形状を表現していると判定する。線又は平面の情報を比較することで判定を行うため、判定が簡単で誤差が蓄積することもなく、確実にメッシュの形状を判定することができる。また、計算が簡単であるために、短い時間で判定を行うことができる。
【００２０】
第２発明においては、第１発明を用いて生成したメッシュの形状を判定し、形状境界集合の中の線又は平面のうち、メッシュ境界集合の中の線又は平面に対応していない線又は平面上の位置に対応する節点を新たに加え、新たなメッシュを生成し、メッシュが図形の形状を表現できるまで繰り返すことにより、図形の形状を表現するメッシュを短時間で確実に生成することができる。
【００２１】
第３及び第４発明においては、デラウニ法を用いてメッシュを生成し、隣接する要素を順番に選択していき、次の要素に移るときの境界が形状境界集合の中の線又は平面に対応する場合に、要素が属する領域を変更して図形外又は図形内に対応する二つの領域のいずれかに分類し、図形外に対応する領域の要素を削除する。これにより、図形の形状を表現するメッシュを短時間で確実に生成することができる。
【００２２】
第５、第７及び第９発明においては、二次元又は三次元の図形の形状を表現する形状モデルの表面上の点に対応する点を節点としてメッシュを生成し、形状モデルの表面を分割した線又は平面を集めた形状境界集合と、メッシュを構成する夫々の要素の境界である線又は平面を集めたメッシュ境界集合とを比較し、形状境界集合の中の線又は平面の夫々がメッシュ境界集合の中の線又は平面のいずれかに対応していない場合は、対応していない線又は平面上の点に対応する節点をメッシュ中に追加してメッシュが図形の形状を表現できるまで繰り返す。次に、メッシュ中の隣接する要素を順番に選択していき、次の要素に移るときの境界が形状境界集合の中の線又は平面に対応する場合に、要素が属する領域を変更して図形外又は図形内に対応する二つの領域のいずれかに分類し、図形外に対応する領域の要素を削除する。線又は平面の情報を比較することでメッシュの形状の判定を行い、形状モデルの表面を示す線又は平面の情報を参照することで要素が属する領域の分類を行うため、判定が簡単で誤差が蓄積することもなく、確実に判定および分類を行うことができる。また、計算が簡単であるために短い時間でメッシュを生成することができる。
【００２３】
【発明の実施の形態】
以下、本発明をその実施の形態を示す図面に基づき具体的に説明する。
図１は、本発明に係るメッシュ生成装置を示すブロック図である。図中１は、コンピュータを用いてなる本発明に係るメッシュ生成装置であり、演算を行うＣＰＵ１１と、ＲＡＭ１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えており、本発明に係るＣＤ−ＲＯＭ等の記録媒体２から本発明に係るコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶し、ＲＡＭ１２にコンピュータプログラム２０をロードし、ＣＰＵ１１はコンピュータプログラム２０に基づいてメッシュ生成装置１に必要な処理を実行する。メッシュ生成装置１は、キーボード又はマウス等の入力装置１５と、液晶ディスプレイ又はＣＲＴディスプレイ等の出力装置１６とを備えており、データの入力を初めとするオペレータからの操作を受け付ける構成となっている。
【００２４】
また、メッシュ生成装置１は、通信インタフェース１７を備え、通信インタフェース１７に接続しているサーバ装置３から本発明に係るコンピュータプログラム２０をダウンロードし、ＣＰＵ１１にて処理を実行する形態であってもよい。
【００２５】
以下に、主に二次元のメッシュを生成する例を用いて、本発明のメッシュ形状判定方法、及びメッシュ形状生成方法を説明する。
図２及び図３は、二次元メッシュを生成する場合のメッシュ生成装置１の処理の流れを示すフローチャートである。メッシュ生成装置１は、まず、オペレータの操作により、メッシュで表現されるべき図形の形状を表現した、ワイヤフレームモデル等の形状モデルの入力を受け付け（Ｓ０１）、受け付けた形状モデルの頂点などの、形状モデルの形状を表現できる代表的な表面上の位置に点を配置する（Ｓ０２）。次に、メッシュ生成装置１は、形状モデルとは別に、点同士の相対位置が形状モデルの表面上に配置した点同士の相対位置と同等になるように、形状モデルの表面上に配置した点の夫々に対応する点を定義する（Ｓ０３）。次に、メッシュ生成装置１は、定義した点を節点としてデラウニ法を用いてメッシュを生成するための、定義した全ての点を内部に包含する三角形である超三角形を作成する（Ｓ０４）。なお、三次元メッシュを生成する場合は、定義した全ての点を内部に包含する四面体である超四面体を作成する。
【００２６】
図４は、点を配置した二次元の形状モデル、及び二次元メッシュを生成するために定義した点の例を示す模式図である。図４（ａ）に示す形状モデルは、表面上の代表的な点である各頂点に、点ＭＰ１〜ＭＰ８が配置されている。また、形状モデル上の点ＭＰ１〜ＭＰ８の夫々に対応する点ＮＰ１〜ＮＰ８が、図４（ｂ）に示すごとく定義されている。更に、点ＮＰ９、ＮＰ１０及びＮＰ１１を結んだ超三角形が定義されており、定義された超三角形に点ＮＰ１〜ＮＰ８の全体が包含されている。点ＮＰ１〜ＮＰ８の相対位置は、ＭＰ１〜ＭＰ８と同等となっており、座標空間上では同じ座標値を有する。
【００２７】
図５及び図６は、二次元メッシュ生成の手順を示す説明図である。次に、メッシュ生成装置１は、定義された点ＮＰ１〜ＮＰ８及び超三角形の頂点ＮＰ９〜ＮＰ１１を節点として、デラウニ法を用いて二次元メッシュを生成する（Ｓ０５）。デラウニ法では、図５（ａ）に示すごとく、三つの節点を頂点とする複数の三角形で空間を分割し、三角形の外接円内に頂点以外の節点を含まないように各三角形を生成する。なお、三次元の場合は、四つの節点を頂点とする複数の四面体で空間を分割し、四面体の外接球内に頂点以外の節点を含まないように各四面体を生成する。
【００２８】
次に、メッシュ生成装置１は、生成した二次元メッシュの各要素の境界の情報を集めたメッシュ境界集合を作成する（Ｓ０６）。図７は、作成されたメッシュ境界集合の内容の例を示す概念図である。二次元メッシュの場合は、要素の境界は線分であるため、図５（ａ）に示す線分ＮＰ１ＮＰ２等の、生成された二次元メッシュ内の境界の夫々が、（ＮＰ１，ＮＰ２）等の、各線分の両端である二つの節点の組にて規定されて記憶されている。なお、三次元の場合は、要素の境界は三角形の平面であるため、各平面の頂点である三つの節点の組にて境界が規定される。次に、メッシュ生成装置１は、形状モデルの表面に配置した点を結んだ線分で形状モデルの表面を分割し、分割した線分を図形の形状を示す境界として集めた形状境界集合を作成する（Ｓ０７）。図８は、作成された形状境界集合の内容の例を示す概念図である。図４（ａ）に示す形状モデルの表面が、表面に配置された点ＭＰ１〜ＭＰ８を両端とする、線分ＭＰ１ＭＰ２〜線分ＭＰ１ＭＰ８の八つの線分に分割され、分割された線分である夫々の境界が、（ＭＰ１，ＭＰ２）等の、各線分の両端である二つの点の組にて規定されて記憶されている。なお、三次元の場合は、形状モデルの表面は、三角形の平面にて分割され、平面の三つの頂点の組にて境界が規定される。
【００２９】
次に、メッシュ生成装置１は、作成したメッシュ境界集合と形状境界集合とを比較し、形状境界集合に含まれる夫々の境界が、メッシュ境界集合に含まれる境界のいずれかに全て対応するか否かを判定する（Ｓ０８）。例えば、形状モデル中の点ＭＰ１及びＭＰ２は、二次元メッシュ中の節点ＮＰ１及びＮＰ２に対応するため、形状境界集合に含まれる境界（ＭＰ１，ＭＰ２）は、メッシュ境界集合に含まれる境界（ＮＰ１，ＮＰ２）に対応する。三次元の場合もまた同様である。
【００３０】
形状境界集合に含まれるいずれかの境界が、メッシュ境界集合に含まれる境界のいずれにも対応していないと判定された場合は、メッシュ生成装置１は、次に、形状境界集合に含まれる境界のうち、メッシュ境界集合に対応しない境界を抽出する（Ｓ０９）。図４（ａ）に示す形状モデルと図５（ａ）に示す二次元メッシュの場合は、対応しない境界は、線分ＭＰ６ＭＰ７及び線分ＭＰ８ＭＰ１となる。次に、メッシュ生成装置１は、形状モデルの抽出した境界上に点を追加する（Ｓ１０）。例えば、図５（ｂ）に示す如く、線分ＭＰ６ＭＰ７及び線分ＭＰ８ＭＰ１上に、中点ＭＰ１２及びＭＰ１３を追加する。なお、三次元の場合は、抽出した境界である三角形の平面上に、例えば重心に点を追加する。次に、メッシュ生成装置１は、図５（ｃ）に示すごとく、形状モデルに追加した点ＭＰ１２及びＭＰ１３に対応する節点ＮＰ１２及びＮＰ１３を二次元メッシュに追加する（Ｓ１１）。次に、メッシュ生成装置１は、処理をステップＳ０５に戻し、形状境界集合に含まれる境界に対応する全ての境界を含んだ図６（ａ）に示す如き二次元メッシュが生成されるまでメッシュ生成を繰り返す。三次元の場合もまた同様にメッシュが生成される。
【００３１】
ステップＳ０８にて、形状境界集合に含まれる全ての境界が、メッシュ境界集合に含まれる境界のいずれかに対応していると判定された場合は、メッシュ生成装置１は、二次元メッシュ上で、形状境界集合に含まれる境界に対応する境界に形状境界を示すフラグを付ける（Ｓ１２）。次に、メッシュ生成装置１は、二次元メッシュ中の超三角形の一辺を含む要素を選択し（Ｓ１３）、選択した要素を、形状モデルが形状を表現する図形外に対応する領域に分類する（Ｓ１４）。例えば、要素ＮＰ１ＮＰ９ＮＰ１１は、超三角形の辺ＮＰ９ＮＰ１１を含み、超三角形の頂点ＮＰ９及びＮＰ１１は図形外に定義されてあって、要素ＮＰ１ＮＰ９ＮＰ１１は図形外に対応する位置にあることは明らかであるため、図形外に対応する領域に分類される。なお、三次元の場合は、超四面体の一面を含む要素を選択し、図形外に対応する領域に分類する。
【００３２】
次に、メッシュ生成装置１は、選択した要素に境界を間にして隣接する要素を選択し（Ｓ１５）、選択した要素と直前に選択していた要素との間の境界に形状境界を示すフラグが付いているか否かを判定し（Ｓ１６）、形状境界を示すフラグが付いていると判定された場合には、直前に選択していた要素が図形外に対応する領域に分類されているときには選択した要素を図形内に対応する領域に分類し、直前に選択していた要素が図形内に対応する領域に分類されているときには選択した要素を図形外に対応する領域に分類して、選択した要素を、直前に選択していた要素と逆の領域に分類する（Ｓ１７）。ステップＳ１６にて、選択した要素と直前に選択していた要素との間の境界に形状境界を示すフラグが付いていないと判定された場合は、メッシュ生成装置１は、選択した要素を、直前に選択していた要素と同じ領域に分類する（Ｓ１８）。次に、メッシュ生成装置１は、全ての要素を分類したか否かを判定し（Ｓ１９）、全ての要素を分類していないと判定された場合は、処理をステップＳ１５へ戻して更に隣接する要素を選択する。
【００３３】
ステップＳ１９にて全ての要素を分類していると判定された場合は、二次元メッシュを構成する夫々の要素は、図６（ｂ）に示すごとく、図形外および図形内に対応する二つの領域に分類され、次に、メッシュ生成装置１は、図形外に対応する領域に分類された要素を削除し（Ｓ２０）、図形の形状を表現した図６（ｃ）に示す如き二次元メッシュを生成して、処理を終了する。三次元の場合も、同様にして図形外に対応する領域に分類された要素が削除され、図形の形状を表現した三次元メッシュが生成される。
【００３４】
本発明に係るメッシュ生成装置１を用いて、以上の手順により二次元または三次元の図形の形状を表現するメッシュが生成される。二次元又は三次元の図形の形状を表現する形状モデルの表面を構成する複数の線又は平面である図形の境界を集めた形状境界集合と、生成したメッシュを構成する夫々の要素の境界を集めたメッシュ境界集合とを比較することでメッシュの形状を判定するため、計算による誤差が蓄積することもなく、確実にメッシュの形状を判定して、図形の形状を表現するメッシュを生成することができる。また、計算が簡単であるために、短い時間でメッシュを生成することができる。
【００３５】
また、デラウニ法を用いて自動でメッシュを生成し、隣接する要素を順に辿って要素の境界が図形の形状の境界に対応するか否かを判定することで、メッシュを構成する要素を図形外または図形内に対応する二つの領域に分類するため、誤差が蓄積するような計算を行うことなく、確実にメッシュを二つの領域に分類し、図形外に対応する領域の要素を削除することで、図形の形状を表現するメッシュを生成することができる。
【００３６】
本実施の形態においては、形状モデルの表面に配置した点に対応する点と、超三角形または超四面体の頂点とを節点としてメッシュを生成する方法を例として示したが、この方法に限るものではなく、形状モデルの内部の点に対応する点を必要に応じて定義して節点とし、メッシュを生成する方法を用いても良い。
【００３７】
【発明の効果】
第１、第６及び第８発明においては、二次元又は三次元の図形の形状を表現する形状モデルの表面を構成する複数の線又は平面を集めた形状境界集合を記憶しておき、生成したメッシュを構成する夫々の要素の境界である線又は平面のメッシュ境界集合と比較し、形状境界集合の中の線又は平面の夫々がメッシュ境界集合の中の線又は平面のいずれかに対応している場合は、メッシュが図形の形状を表現していると判定する。線又は平面の情報を比較することで判定を行うため、判定が簡単で誤差が蓄積することもなく、確実にメッシュの形状を判定することができる。また、計算が簡単であるために、短い時間で判定を行うことができる。
【００３８】
第２発明においては、第１発明を用いて生成したメッシュの形状を判定し、形状境界集合の中の線又は平面のうち、メッシュ境界集合の中の線又は平面に対応していない線又は平面上の位置に対応する節点を新たに加え、新たなメッシュを生成し、メッシュが図形の形状を表現できるまで繰り返すことにより、図形の形状を表現するメッシュを短時間で確実に生成することができる。
【００３９】
第３及び第４発明においては、デラウニ法を用いてメッシュを生成し、隣接する要素を順番に選択していき、次の要素に移るときの境界が形状境界集合の中の線又は平面に対応する場合に、要素が属する領域を変更して図形外又は図形内に対応する二つの領域のいずれかに分類し、図形外に対応する領域の要素を削除する。これにより、図形の形状を表現するメッシュを短時間で確実に生成することができる。
【００４０】
第５、第７及び第９発明においては、二次元又は三次元の図形の形状を表現する形状モデルの表面上の点に対応する点を節点としてメッシュを生成し、形状モデルの表面を分割した線又は平面を集めた形状境界集合と、メッシュを構成する夫々の要素の境界である線又は平面を集めたメッシュ境界集合とを比較し、形状境界集合の中の線又は平面の夫々がメッシュ境界集合の中の線又は平面のいずれかに対応していない場合は、対応していない線又は平面上の点に対応する節点をメッシュ中に追加してメッシュが図形の形状を表現できるまで繰り返す。次に、メッシュ中の隣接する要素を順番に選択していき、次の要素に移るときの境界が形状境界集合の中の線又は平面に対応する場合に、要素が属する領域を変更して図形外又は図形内に対応する二つの領域のいずれかに分類し、図形外に対応する領域の要素を削除する。線又は平面の情報を比較することでメッシュの形状の判定を行い、形状モデルの表面を示す線又は平面の情報を参照することで要素が属する領域の分類を行うため、判定が簡単で誤差が蓄積することもなく、確実に判定および分類を行うことができる。また、計算が簡単であるために短い時間でメッシュを生成することができる等、本発明は優れた効果を奏する。
【図面の簡単な説明】
【図１】本発明に係るメッシュ生成装置を示すブロック図である。
【図２】二次元メッシュを生成する場合のメッシュ生成装置の処理の流れを示すフローチャートである。
【図３】二次元メッシュを生成する場合のメッシュ生成装置の処理の流れを示すフローチャートである。
【図４】点を配置した二次元の形状モデル、及び二次元メッシュを生成するために定義した点の例を示す模式図である。
【図５】二次元メッシュ生成の手順を示す説明図である。
【図６】二次元メッシュ生成の手順を示す説明図である。
【図７】作成されたメッシュ境界集合の内容の例を示す概念図である。
【図８】作成された形状境界集合の内容の例を示す概念図である。
【図９】従来の包含判定の方法を示す模式図である。
【符号の説明】
１  メッシュ生成装置
２  記録媒体
２０  コンピュータプログラム
【図１】
0003890214.tif 000002
【図２】
0003890214.tif 000003
【図３】
0003890214.tif 000004
【図４】
0003890214.tif 000005
【図５】
0003890214.tif 000006
【図６】
0003890214.tif 000007
【図７】
0003890214.tif 000008
【図８】
0003890214.tif 000009
【図９】
0003890214.tif 000010