(57)【要約】  プライマリ幾何オブジェクトおよびそれらのファセットから幾何モデルを作成する目的でコンピュータを使用してブーリアン演算を実行すること。本方法は、ファセットの交線を計算するステップと、交線が通過するファセットを分割するステップと、各ファセットが見えているか隠れているかを判定するステップと、ファセットを再編成して１つまたは複数の幾何オブジェクトを形成するステップと、を含む。本方法は、ＣＡＤ／ＣＧ／ソリッドモデリングシステムにおいて最も使用されているデータ構造であるＣＳＧおよびＢ−ＲＥＰを利用せず、しかしながらＣＳＧおよびＢ−ＲＥＰの両方の利点を有し、すなわち実施が容易であり柔軟性が高い。これに加えて、本方法は、ソリッドモデリングシステムおよびサーフェスモデリングシステムのための統合された方法であり、この統合された方法は、編集可能なさまざまなモデルを生成することができる。
2019526111.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステム内で実施されかつコンピュータによって動作する、幾何ファセットを使用する直接的なブーリアン演算を実行する方法であって、
レンダリングファセットを、隣接三角形を含む拡張された三角形にマッピングするステップと、
２つの最小バウンディングボックスが重なるかを検出し、エッジと三角形の交差を実行することによって、交線の始点を保持する最初の三角形ペアを探索するステップと、
隣接する三角形を探索することによって前記交線が閉じる、または、すべての三角形が横切られるまで前記交線を延長するステップと、
交線が通過する三角形を分割するステップと、
ファセットを再編成し、ブーリアン演算のタイプに従って三角形を削除および維持するステップと、
拡張された三角形をレンダリングファセットにマッピングするステップと、
を含む方法。
【請求項２】
結合、交差、除外、差および分割を含む任意のブーリアン演算が、データ構造である空間領域構成法（ＣＳＧ）および境界表現（Ｂ−ＲＥＰ）を用いずに、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリング三角形にマッピングされる、
請求項１に記載の方法。
【請求項３】
結合、交差、除外、差および分割を含む任意のブーリアン演算が、データ構造ＣＳＧおよびＢ−ＲＥＰを用いて、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリング三角形にマッピングされる、
請求項１に記載の方法。
【請求項４】
交点が正確であり、かつ、交線が近似的な曲がったエッジラインではないように、交線を構築するステップが、２つのファセットが重ならないかを前記最小バウンディングボックスを使用して検出し、エッジと三角形の交差の計算を実行する、
請求項１に記載の方法。
【請求項５】
エッジと三角形の交差の直接的な計算が、点が三角形のエッジ上であるかを確認することに置き換えられるように、交点を探索するステップが、エッジと三角形の交差を計算し、かつ、隣接するファセットを採用する、
請求項１に記載の方法。
【請求項６】
三角形を分割するステップが、すべての３次元三角形およびそのすべてのサブ交線を２次元平面上に投影し、かつ、修正されたＷａｔｓｏｎ法によってドロネー２Ｄメッシュを構築し、前記修正されたＷａｔｓｏｎ法においては、たとえ前記サブ交線が凸状ではないときにも三角形が異なる区画に分割される、
請求項１に記載の方法。
【請求項７】
Ａに属する三角形Ｔａが幾何オブジェクトＢと境界を接しているかをチェックするステップが、ｔ−バッファを利用し、さらに、
Ｔａの重心ｃを計算するステップと、
前記重心ｃを通過しかつＴａの法線に沿った線ｌ：ｐ＝ｃ＋ｔ＊Ｎを構築するステップと、
オブジェクトＢの各三角形Ｔｂについて、ｌが内点ｐにおいてＴｂと交差するかをチェックしてｔをｔ−バッファに追加するステップと、
ｔ−バッファの中の負のｔのサイズが正のｔのサイズに等しいときにＴａを「隠れている」に設定するステップと、
を含む、
請求項１に記載の方法。
【請求項８】
サーフェスパッチをトリムするときに三角形が「隠れている」かどうかをチェックするステップが、
関与するパッチのＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの正則点のｍ＿ＩＤを０に設定し、前記パッチの交線の点のｍ＿ＩＤを、前記線とトリム輪郭が同じ方向であるかに応じて昇順または降順に設定するステップと、
各三角形のメンバーｍ＿Ｐｏｉｎｔｓのｍ＿ＩＤに従って、各三角形が境界三角形であるかを判定するステップと、
各境界三角形について、前記境界三角形が前記トリム輪郭の左側であるか右側であるかを判定し、境界三角形ではない隣接三角形を「左」または「右」に設定するステップと、
をさらに含む、
請求項１に記載の方法。
【請求項９】
結合、交差、除外、差または分割などのブーリアン演算が、その演算結果を構築するために、見えているファセット、または、隠れているファセット、または、見えているファセットおよび隠れているファセットの混合、を維持する、
請求項１に記載の方法。
【請求項１０】
ブーリアン演算結果が、表示されるようにレンダリングデータに直接マッピングされ、かつ、次のブーリアン演算にデータを提供する、
請求項１に記載の方法。
【請求項１１】
幾何オブジェクトのレンダリングファセットを使用する直接的なブーリアン演算を実行する、ハードウェアおよびソフトウェアからなるコンピュータシステムであって、
前記システムが、データおよびコマンドを入力するための入力装置と、ユーザインタフェース、幾何オブジェクト、およびさらなるデータを表示する表示装置と、幾何データと、ソフトウェアシステムを構成する命令とを記憶する媒体と、前記命令を部分的または完全に埋め込んでいるマイクロチップまたは集積回路と、計算を実行するプロセッサと、を有する前記コンピュータ、を備えており、
前記計算が、
スイープされた幾何オブジェクトおよび押し出された幾何オブジェクトを含むプライマリ幾何オブジェクトを作成する、修正する、または、ロードして、前記プライマリ幾何オブジェクトを、前記コンピュータの入力装置によってさまざまな位置または向きに再配置するステップと、
前記幾何オブジェクトの２つを選択するステップと、
レンダリングファセットを、隣接三角形を含む拡張された三角形にマッピングするステップと、
２つの最小バウンディングボックスが重なるかを検出することによってと、エッジと三角形の交差を実行することによって、交線の始点を保持する最初の三角形ペアを探索するステップと、
隣接する三角形を探索することによって前記交線が閉じる、またはすべての三角形が横切られるまで、前記交線を延長するステップと、
交線が通過するファセットを分割するステップと、
ファセットを再編成し、ブーリアン演算のタイプに従ってファセットを削除、維持、およびマージするステップと、
拡張された三角形をレンダリング三角形にマッピングするステップと、
からなる、
コンピュータシステム。
【請求項１２】
結合、交差、除外、差および分割を含む任意のブーリアン演算が、データ構造であるＣＳＧおよびＢ−ＲＥＰを用いずに、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリングデータにマッピングされる、
請求項１１に記載のシステム。
【請求項１３】
結合、交差、除外、差および分割を含む、任意のブーリアン演算が、データ構造ＣＳＧおよびＢ−ＲＥＰを用いて、幾何オブジェクトのレンダリングファセットを使用して新しい幾何オブジェクトを作成し、その結果がただちにレンダリングデータにマッピングされる、
請求項１１に記載のシステム。
【請求項１４】
交点が正確であり、かつ、交線が近似的な曲がったエッジラインではないように、交線を構築するステップが、２つのファセットが重ならないかを前記最小バウンディングボックスを使用して検出し、エッジと三角形の交差の計算を実行する、
請求項１１に記載のシステム。
【請求項１５】
エッジと三角形の交差の直接的な計算が、点が三角形のエッジ上であるかを確認することに置き換えられるように、交点を探索するステップが、エッジと三角形の交差を計算し、かつ、隣接する三角形を採用する、
請求項１１に記載のシステム。
【請求項１６】
三角形を分割するステップが、すべての３次元三角形およびそのすべてのサブ交線を２次元平面上に投影し、かつ、ドロネー２Ｄメッシュを構築し、前記ドロネー２Ｄメッシュにおいては、たとえ前記サブ交線が凸状ではないときにも三角形が異なる区画に分割される、
請求項１１に記載のシステム。
【請求項１７】
Ａに属する三角形Ｔａが幾何オブジェクトＢと境界を接しているかをチェックするステップが、ｔ−バッファを利用し、さらに、
Ｔａの重心ｃを計算するステップと、
前記重心ｃを通過しかつＴａの法線に沿った線ｌ：ｐ＝ｃ＋ｔ＊Ｎを構築するステップと、
オブジェクトＢの各三角形Ｔｂについて、ｌが内点ｐにおいてＴｂと交差するかをチェックしてｔをｔ−バッファに追加するステップと、
ｔ−バッファの中の負のｔのサイズが正のｔのサイズに等しいときにＴａを「隠れている」に設定するステップと、
を含む、
請求項１１に記載のシステム。
【請求項１８】
サーフェスパッチをトリムするときに三角形が「隠れている」かどうかをチェックするステップが、
関与するパッチのＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの正則点のｍ＿ＩＤを０に設定し、前記パッチの交線の点のｍ＿ＩＤを、前記線とトリム輪郭が同じ方向であるかに応じて昇順または降順に設定するステップと、
各三角形のメンバーｍ＿Ｐｏｉｎｔｓのｍ＿ＩＤに従って、各三角形が境界三角形であるかを判定するステップと、
各境界三角形について、前記境界三角形が前記トリム輪郭の左側であるか右側であるかを判定し、境界三角形ではない隣接三角形を「左」または「右」に設定するステップと、
をさらに含む、
請求項１１に記載のシステム。
【請求項１９】
結合、交差、除外、差または分割などのブーリアン演算が、その演算結果を構築するために、見えているファセット、または、隠れているファセット、または、これら２つのタイプの幾何ファセットの混合、を維持する、
請求項１１に記載のシステム。
【請求項２０】
ブーリアン演算結果が、表示されるようにレンダリングデータに直接マッピングされ、かつ、次のブーリアン演算にデータを提供する、
請求項１１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、製品の設計、製造、およびシミュレーションにおいて幅広く使用されているコンピュータ支援設計（ＣＡＤ：Computer Aided Design）、コンピュータグラフィックス（ＣＧ：Computer Graphics）、ソリッドモデリング（Solid Modeling）システム、およびサーフェスモデリング（Surface Modeling）システムに、プライマリ幾何オブジェクトから３次元幾何モデルを構築するための直接的なブーリアン演算法を提供する。機械工業、カルチャー、スポーツなど、幾何形状が存在するあらゆるところでＣＡＤ／ＣＧアプリケーションを導入することができる。
【背景技術】
【０００２】
コンピュータハードウェアは極めて高度に発展しているため、普通のパーソナルコンピュータ（ＰＣ）（Personal Computer）さえも、商用ＣＡＤ／ＣＧシステム（通常ではＡＮＤ、ＯＲ、およびＮＯＴを含むブーリアン演算機能を有する）をインストールして動作させる目的に使用することができる。ＰＣの構成要素は、入力装置（マウスおよびキーボードなど）、メインマシン、画面、およびプリンタを備える。ソフトウェアシステムは、幾何学機能および非幾何学機能を含む。図１は、ＰＣの主要な構成要素を示しており、図２Ａ〜図２Ｄは、一般的なＣＡＤ／ＣＧソフトウェアシステムのアーキテクチャを示している。
【０００３】
ブーリアン演算は、さまざまな幾何形状（プライマリ幾何オブジェクト、スイープされたオブジェクト、または押し出されたオブジェクトを含む）から複雑なソリッド幾何オブジェクトを構築する一般的なプロセスを、ＣＡＤ／ＣＧ／ソリッドモデリングシステムに提供する。Ｌｅｅ氏は、サーフェスを分割する目的にブーリアン演算を適用した（特許文献１参照）。
【０００４】
ブーリアン演算は、プライマリ幾何オブジェクトおよび演算順序を階層的な方法で記録するために空間領域構成法（ＣＳＧ：Constructive Solid Geometry）（これは技術的に実施が容易である）に依拠することができ、これに対して境界表現（Ｂ−ＲＥＰ：Boundary Representation）は、より多くの幾何オブジェクトタイプ（延長されたジオメトリなど）をサポートする、より柔軟な方法とみなされる（非特許文献１参照）。
【０００５】
本発明は、５つのブーリアン演算コマンド、すなわち、結合、交差、除外、差、分割を提示し、これらは、レンダリング機能に使用される幾何ファセットから分解された三角形に対して直接機能し、データ構造である空間領域構成法または境界表現を必要としない。本発明において定義されるデータ構造は、少数の単純なクラスであり、本発明において組み込まれるアルゴリズムは、簡潔であり実施が容易であり、５つのコマンドによってユーザは、幾何オブジェクトのタイプを選択することによってのみならず、幾何オブジェクトのファセットを定義することによっても、幾何モデルを作成することができる。図３は、６つのファセットを有する直方体と球とを示しており、異なるファセットによって異なる結果になる。
【０００６】
５つのコマンドは、ソリッドモデリングおよびサーフェスモデリング用に設計されているが、本発明に組み込まれているサーフェストリムコマンドは、サーフェスモデリングのための代替方法を提供し、ファセットが隠れているかをさまざまな方法で識別する。
【０００７】
本発明は、ＣＳＧおよびＢ−ＲＥＰとは異なるデータ構造およびアルゴリズムを提示し、本発明に組み込まれているアルゴリズムには、三角形と三角形を交差させる、サブ交線（sub-intersection line）によって三角形を分割する、ファセットが隠れているかを識別する、三角形を再編成して幾何モデルを形成する、が含まれる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許第６，３０７，５５５号明細書（２００１年１０月）、Ｌｅｅ、３４５／４２３
【非特許文献】
【０００９】
【非特許文献１】"Boolean Set Operations on Non-Manifold bounding Representation Objects", E. Gursoz et al., Computer-Aided Design 23 (1991) Jan./Feb. No. 1 London, GB
【非特許文献２】"Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopest", D.F. Watson, The Computer Journal 24 (2) 1981
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明は、ブーリアン演算を実行するための一連のデータ構造および一連のアルゴリズムを提供し、複雑な幾何モデルを構築することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、ブーリアン演算を実行するための一連のデータ構造および一連のアルゴリズムを提供し、これらは複雑な幾何モデルを構築するために使用され、コンピュータハードウェアおよびレンダリング機能（ＯｐｅｎＧＬライブラリなど）によってレンダリングデータとして使用される幾何ファセットから分解された三角形に対して直接機能する。幾何形状（例えば球、円錐、円柱、直方体、三角形のファセット、押し出されたオブジェクトまたはスイープされたオブジェクト、サーフェスパッチ）は、表示するために三角形に分けられてセット（ＴｒｉａｎｇｌｅＳｅｔと称する）を構築する。ブーリアン演算を実行するために２つの幾何形状を選択すると、隣接する三角形がＴｒｉａｎｇｌｅＳｅｔ内の各三角形に追加され、形状それぞれのための別のセットＢｌＯｐＴｒｉａｎｇｌｅＳｅｔが形成される。
【００１２】
本発明に記載されているブーリアン演算の第２のステップでは、三角形セットの間で交線を探索して構築する。このステップでは、最初に、交差する三角形の最初のペアを見つける。本システムは、各三角形に対して、軸線に合わせた最小バウンディングボックス（bounding box）を構築し、２つのバウンディングボックスが重なっているかをチェックして、エッジと三角形の交差を計算する必要があるかを判定する。エッジと三角形の（１つまたは複数の）交点が三角形の内側にあるとき、本システムは探索タスクを完了し、点データを交線セットに格納する。
【００１３】
現在の交線を延長するため、本方法は、隣接する三角形をトレースし、交線が閉じるまでエッジと三角形の交点を計算する。
【００１４】
本発明に記載されているブーリアン演算の第３のステップでは、三角形を分割する。交線の各線分は２つの三角形を参照し、これらの三角形それぞれが、三角形を３つ以上のより小さい三角形に分割する１つまたは複数の線分を含む少なくとも１本のサブ交線を有する。三角形を分割した後、元の三角形が除去され、分割された小さい三角形がＢｌＯｐＴｒｉａｎｇｌｅＳｅｔに追加される。
【００１５】
本発明に記載されているブーリアン演算の第４のステップでは、各三角形が隠れているか見えているかを判定する。ある三角形が別の三角形によって囲まれている場合、その三角形は隠れている。三角形が見えているとは、その三角形が別のオブジェクトの外側であることを意味する。
【００１６】
本発明に記載されているブーリアン演算の第５のステップでは、三角形を再編成する。三角形のいくつかを除去しなければならず、三角形のいくつかをまとめる必要があり、再編成には５つのケースがある。
【００１７】
本発明に記載されているブーリアン演算の最後のステップでは、ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔをＴｒｉａｎｇｌｅＳｅｔにマッピングする。
【００１８】
このサーフェストリムコマンドのプロセスも、６つのステップを含む。最初に、本システムは、サーフェスをＢｌＯｐＴｒｉａｎｇｌｅＳｅｔにマッピングし、そのトリム輪郭の１つを押し出された形状にマッピングして、ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔを形成する。ステップ２、ステップ３、およびステップ６は、ブーリアン演算のステップと同じである。ステップ４では、三角形がトリム輪郭の左側であるか右側であるかをチェックし、それを維持する必要があるかを判定する。再編成機能（ステップ５）は、システムがサーフェスをトリムするときに左側の三角形のみ、または右側の三角形のみを削除する。
【図面の簡単な説明】
【００１９】
【図１】図１は、パーソナルコンピュータの主要な構成要素を示しており、これらは、一般的にはメインマシン、入力装置（マウスおよびキーボードを含む）、ディスプレイ、およびプリンタを含む。高度に発展したＣＡＤ／ＣＧシステムは、ＰＣマシン上で動作することができる。
【図２】図２Ａ、図２Ｂ、図２Ｃおよび図２Ｄは、ＣＡＤ／ＣＧ／幾何モデリングシステムがブーリアン演算およびサーフェストリムを使用して幾何モデルを構築するためのソフトウェアアーキテクチャを示している。
【図３】図３は、ファセットの元の幾何オブジェクトのタイプおよびサイズがたとえ同じであっても、異なるファセットがさまざまな結果をもたらす状況を表している。左側の例は、より少ないファセットを有し、右側は、より多くのファセットを有する。これらの例では、ブーリアン交差演算が直方体および球に対して機能している。
【図４】図４は、幾何ファセットを使用する直接的なブーリアン演算（immediate Boolean operation）の流れ図である。
【図５】図５は、三角形が３つの隣接三角形を有することを示している。三角形とその２つの頂点が与えられると、ソリッドモデルにおいてただ１つの隣接する三角形が存在する。
【図６】図６Ａおよび図６Ｂは、２つの最小バウンディングボックスが重ならない場合と、２つのバウンディングボックスが互いに重なる場合を示している。各三角形は仮想的に最小バウンディングボックスを有する。２つのボックスが重ならない場合、それら２つのボックスに含まれている三角形は交差しない。ボックスが重なる場合、エッジと三角形の交差を計算する必要がある。
【図７】図７Ａ、図７Ｂおよび図７Ｃは、エッジと三角形が交差する３つの場合、すなわち、交点が三角形の内側である場合、交点が三角形のエッジ上に位置する場合、交点が三角形の頂点である場合、を示している。
【図８】図８Ａ、図８Ｂ、図８Ｃおよび図８Ｄは、探索候補セットを示している。探索候補セットによってシステムは、エッジと三角形の計算を行うことにより次の三角形を横切って交線を延長することができる。塗りつぶされている三角形は、互いに交差する三角形の最後のペアであり、塗りつぶされていない三角形は、データ構造Ｔｒｉａｎｇｌｅ３ｄＥｘのメンバーｍ＿ＮｅｉｇＴｒｉによって参照されており、塗りつぶされていない三角形は、交線を構築するときに三角形の最小のセットを探索するようにシステムをガイドする。セットは、１つの三角形または２つの三角形を含む、または三角形を含まない。
【図９】図９Ａ、図９Ｂ、図９Ｃおよび図９Ｄは、交線の４つの例を示している。直方体が球と交差し、球が異なるファセット数を有する。
【図１０】図１０Ａ、図１０Ｂおよび図１０Ｃは、サブ交線の３つの例を、濃い色で示している。図１０Ａは１本のサブ交線、図１０Ｂは２本のサブ交線、図１０Ｃは１本のサブ交線を有する。
【図１１】図１１Ａ、図１１Ｂ、図１１Ｃおよび図１１Ｄは、三角形がサブ交線によって一連の三角形に分割されている４つの例を示している。
【図１２】図１２Ａ、図１２Ｂ、図１２Ｃ、図１２Ｄ、図１２Ｅ、図１２Ｆ、図１２Ｇおよび図１２Ｈは、メッシュに各交点が段階的に挿入されるドロネー（Ｄｅｌａｕｎａｙ）メッシュシーケンスを示している。
【図１３】図１３は、図１２Ａ乃至図１２Ｈのシーケンスを作成した、ドロネーメッシュＷａｔｓｏｎ法（Delaunay mesh Watson method）の流れ図である。
【図１４】図１４は、三角形とそのドロネーメッシュを示している。元の三角形が除去され、後の計算用にドロネーメッシュのみが維持される。
【図１５】図１５は、ｔ−バッファを示している（ｔは負または正）。ｔ−バッファ内で負のｔと正のｔのサイズが釣り合っている場合、関与する三角形は、別のオブジェクトによって閉じられており隠れている。
【図１６】図１６Ａ〜図１６Ｅは、直方体と球を使用して行われるブーリアン演算の５つの例を示している。図１６Ｆおよび図１６Ｇは、２つのブーリアン演算（結合および除外）の結果の内部メッシュを示している。
【図１７】図１７は、閉じたサーフェス（変形した球）が輪郭線によってトリムされ、２つの孔を生成する状況を示している。
【図１８】図１８は、押し出されたサーフェス（管）が輪郭線によってトリムされ、孔を作成する例を示している。
【発明を実施するための形態】
【００２０】
本発明は、幾何オブジェクトをレンダリングするためにファセットを格納するＰｏｉｎｔ３Ｄ、Ｔｒｉａｎｇｌｅ３Ｄ、Ｔｒｉａｎｇｌｅ３ｄＳｅｔを継承するデータ構造Ｐｏｉｎｔ３ｄＥｘ、Ｔｒｉａｎｇｌｅ３ｄＥｘ、およびＢｌＯｐＴｒｉａｎｇｌｅ３ｄＳｅｔを定義する。システムは、ブーリアン演算を実行するとき、レンダリングファセットをＢｌＯｐＴｒｉａｎｇｌｅ３ｄＳｅｔにマッピングし、その後のすべてのプロセスは、ＢｌＯｐＴｒｉａｎｇｌｅ３ｄＳｅｔのメンバーおよび属性に焦点をあてる。図４は、本発明によって行われるブーリアン演算の主な手順を記述した流れ図である。システムは、ブーリアン演算が完了した後、ＢｌＯｐＴｒｉａｎｇｌｅ３ｄＳｅｔに格納された結果をレンダリングファセットにマッピングする。
【００２１】
＜レンダリングのための幾何ファセット＞
ＣＡＤシステムは、幾何オブジェクト（球、円錐、直方体、円柱、押し出されたオブジェクト、またはスイープされたオブジェクトなど）を表すためにファセットをレンダリングする。ファセットは３つ以上の点から構成される。ファセットは、通常では計算を容易にするため三角形に分解される。直方体は、１２の三角形に分解される６つのファセットを有する。球は、２４の三角形を構成する１８のファセットを有することができる。球は、１０００より多くのファセットおよび三角形を使用してレンダリングすることもできる。図３は、さまざまなファセットを使用してレンダリングされた球を示している。本方法では、幾何オブジェクトをレンダリングする目的で三角形セットのデータ構造を記述するためにＴｒｉａｎｇｌｅ３ｄＳｅｔを使用し、Ｔｒｉａｎｇｌｅ３ｄＳｅｔは、２つの属性、すなわち３次元の点セットおよび三角形セットを含み、この場合、Ｔｒｉａｎｇｌｅ３ｄがＰｏｉｎｔ３ｄを参照する。
class Triangle3dSet
{
DataSet<Point3d>     m_PointSet;
DataSet<Triangle3d>   rn_TriangleSet;
};
class Triangle3d
{
Point3d     *m_Points[3];
};
class Point3d
{
DataTypeI m_X, m_Y, m_Z;
};
【００２２】
＜ブーリアン演算のための三角形＞
本発明に記載されているブーリアン演算法では、３つの主要クラス、すなわちＢｌＯｐＴｒｉａｎｇｌｅＳｅｔ、Ｔｒｉａｎｇｌｅ３ｄＥｘ、およびＰｏｉｎｔ３ｄＥｘを定義する。
class BlOpTriangleSet
{
DataSet<Point3dEx>     m_PointSet;
DataSet<Triangle3dEx>   m_TriangleSet;
};
class Point3dEx : Point3d
{
DataTypell   m ID; //位置および順序のインデックス
DataTypelll  m_X, m_Y, m_Z; //ＤａｔａＴｙｐｅｌｌｌはＤａｔａＴｙｐｅｌと異なっていてよい
};
class Triangle3dEx : Triangle3d
{
Point3dEx    *m_Points[3];
DataTypell    m_ID;
Plane        m_Plane;
DataTypelV   m_Normal[3];
Triangle3dEx  *m_NeigTri[3]; //隣接する三角形
};
【００２３】
ＤａｔａＴｙｐｅｌｌは、ｉｎｔ、ｌｏｎｇ、ｕｎｓｉｇｎｅｄ  ｌｏｎｇ、または他の整数型とすることができる。Ｄａｔａｌｙｐｅｌｌｌは、浮動小数点数データ型（ｆｌｏａｔ、ｄｏｕｂｌｅ、さらにはｌｏｎｇ  ｄｏｕｂｌｅなど）である。
【００２４】
クラスＴｒｉａｎｇｌｅ３ｄＥｘは、各三角形が３つの隣接する三角形を有しうることを指定し、すべての三角形それぞれのただ１つのコピーがＢｌＯｐＴｒｉａｎｇｌｅＳｅｔに格納される。直方体を例に挙げれば、最も単純な場合、直方体は１２の三角形を有し、たとえ各三角形が３つの隣接三角形を有してもＢｌＯｐＴｒｉａｎｇｌｅＳｅｔは依然として合計で１２の三角形を格納する。
【００２５】
技術的には、Ｔｒｉａｎｇｌｅ３ｄは属性ｍ＿Ｎｏｒｍａｌを有することができる。ＤａｔａＴｙｐｅｌとＤａｔａＴｙｐｅｌＶが同じ型（例えばｄｏｕｂｌｅ）である場合、属性ｍ＿Ｎｏｒｍａｌを継承することができる。
【００２６】
＜データのマッピング＞
Ｔｒｉａｎｇｌｅ３ｄＳｅｔをＢｌＯｐＴｒｉａｎｇｌｅＳｅｔにマッピングするプロセスでは、レンダリング像（rendering statue）からの点セットおよび三角形セットをコピーし、デフォルトの属性を与える。データのマッピングは、以下の手順を含む。
１）Ｔｒｉａｎｇｌｅ３ｄＳｅｔからの点をＢｌＯｐＴｒｉａｎｇｌｅＳｅｔにコピーし、このとき同じ点が存在しないようにする。
２）Ｔｒｉａｎｇｌｅ３ｄＳｅｔからの三角形をＢｌＯｐＴｒｉａｎｇｌｅＳｅｔにコピーする。
３）ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの中の各三角形について、その隣接する三角形を設定する。
４）ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの中の各三角形について、法線を計算し、平面方程式を確立する。
【００２７】
注１：  ２点ａ，ｂが与えられたとき、｜ｘａ−ｘｂ｜＜εかつ｜ｙａ−ｙｂ｜＜ε（εは正の浮動小数点数、例えば５．０ｅ−１６）ならば、ｂはａと同じである。
【００２８】
注２：  レンダリングデータからの点をＢｌＯｐＴｒｉａｎｇｌｅＳｅｔにマッピングするとき、システムは、ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの中に同じ点が存在するかをチェックする。
【００２９】
注３：  三角形（３つの点を有する）は、数式がａｘ＋ｂｙ＋ｃｚ＋ｄ＝０である平面を定義し、クラスＰｌａｎｅは、その平面を４つの数の配列（ｍ＿ＡＢＣＤ［４］など）として内部的に記録する。
【００３０】
注４：  三角形は、その３点が同じでない場合、つねに有効な法線を有する。たとえ三角形がｍ＿ＡＢＣＤに関連していても、個別にコピーすることによって明確性が高まり、後から扱うときにも容易である。
【００３１】
注５：  すべての三角形は３つのエッジを有し、重複する点が存在しないとき、その三角形はソリッドモデルにおいて３つの隣接する三角形を有する。図５は一例を示している（塗りつぶされた三角形およびその３つの隣接三角形）。サーフェストリムのためのサーフェスパッチに関与するとき、三角形の１つまたは２つの隣接三角形がヌルであってもよい。
【００３２】
＜第１の交点＞
すべての三角形は３つの頂点を有し、これらの頂点は最小バウンディングボックスを定義する。本方法では、軸線に合わせた最小バウンディングボックスのコンセプトを採用した。
【００３３】
三角形のペアが与えられたとき、それらのバウンディングボックスが重ならない場合、２つの三角形は交点を持たない。そうでない場合、本方法ではエッジと三角形の交差の計算を実行する。
【００３４】
三角形Ｔａのエッジが、三角形Ｔｂによって定義される平面と交差し、かつ交点ｐｅｔがＴｂの内側である場合、ｐｅｔは第１の交点である。ｐｅｔがＴｂの外側である場合、ペアにおける三角形の位置を交換し（（Ｔａ，Ｔｂ）を（Ｔｂ，Ｔａ）に変更する）、エッジと三角形の交差の計算を行う。
【００３５】
三角形Ｔａのｉ番目（ｉ∈［０，２］）のエッジ（その式はｐ＝ｐｉ＋ｔ＊（ｐ（ｉ＋１）％３−ｐｉ）である）と、三角形Ｔｂによって定義される平面（その式はａｘ＋ｂｙ＋ｃｚ＋ｄ＝０である）とが与えられたとする。２つの式が解を持つ場合、エッジは平面と交差する。エッジと平面の交点が三角形Ｔｂの内側である場合、その点はエッジと三角形の交点である。
【００３６】
＜交線の延長＞
本方法では、交点をＰｎｔＥｇＴｒｉとして記録するためのデータ構造を定義する。
class PntEgTri
{
Triangle3dEx  *m_Tri0, *m_Tri1;
DataTypell    m_Edgelndex;
DataTypell    m_PointPosi;
Point3dEx    m_Point;
Point3dEx    *m_PntGlobalIndexA, *m_PntGlobalIndexB;
};
【００３７】
ＰｎｔＥｇＴｒｉ（簡潔にはｐｅｔ）は、三角形における交点の位置に従って、図７Ａ〜図７Ｃに示した３つのカテゴリに分類することができる。
１）最も一般的なケースは、エッジと三角形が交差する場合であり、ｐｅｔは、三角形Ｔａのエッジ上、かつ三角形Ｔｂの内側に位置する。
２）エッジとエッジが交差する場合、ｐｅｔは、三角形Ｔａのエッジ上、かつ三角形Ｔｂのエッジ上に位置する。
３）エッジと頂点が交差する場合、ｐｅｔは、三角形Ｔａのエッジ上、かつ三角形Ｔｂの頂点に位置する。
【００３８】
交線を延長するため、本システムでは、次の（１つまたは複数の）隣接する三角形を認識し、交線が閉じる、またはすべての三角形が横切られるまで、エッジと三角形の交差をチェックする。
【００３９】
＜サブ交線＞
交線は一連の三角形を通過し、各三角形を複数の区画（partition）に分割する。三角形の内側の交線の線分がサブ交線を構成する。図１０Ａ〜図１０Ｃは、３つの例を示しており、濃い色の線がサブ交線である。実際には、三角形は、０本、１本、２本、または３本のサブ交線を有することができる。
【００４０】
次のアルゴリズムは、少なくとも１本のサブ交線を有する三角形への有効な参照を得る方法を示している。
【００４１】
各交線において、
各交点について、三角形の参照を得る（ｍ＿Ｔｒｉ０，ｍ＿Ｔｒｉ１）
三角形ペアの各三角形において、その三角形が分割されない場合、
各交線において、
サブ交線を探索して構築する。
【００４２】
有効な三角形と交線が与えられたとき、ｐｅｔがその三角形のサブ交線に属するかを判定するため、本方法は以下をチェックする。
１）ｐｅｔが三角形のエッジ上であるか
２）またはｐｅｔが三角形の内側であるか
３）またはｐｅｔが三角形の頂点に等しいか
【００４３】
＜三角形の分割＞
一連のサブ交線が与えられたとき、三角形を分割するため、本方法は、
１）重複しているｐｅｔを除去する。隣り合うｐｅｔが同じである場合、本方法は１つのコピーのみを維持する。
２）最後のｐｅｔの位置を識別する。各ｐｅｔが三角形のどのエッジ上に位置しているかをチェックする。
３）三角形の上側区画、下側区画、および中央区画に分割する（適用可能な場合）。
【００４４】
三角形の区画を表す平面上の一連の点が与えられたとき、その平面を三角形のグループに分解するため、本方法では、１９８１年に公開されたドロネー２ＤメッシュＷａｔｓｏｎ法を修正する［非特許文献２］。
【００４５】
ドロネー２Ｄメッシュは、３つのデータセット、すなわち、生成された三角形を保持する三角形セットと、直前に削除された三角形を格納する削除三角形セットと、削除三角形セットのアウトラインを記録するポリゴン、を有する。
【００４６】
修正されたドロネー２Ｄメッシュ法は、以下のステップを含む。
１）サブ交線と三角形の頂点を結ぶアウトライン点列を構築する（適用可能な場合）。
２）この３次元点列を、平面の向きに従って２次元点列にマッピングする。
３）４つの点を加えて、２次元の点すべてを囲む、より大きいバウンディングボックスを形成する。
４）バウンディングボックスの１本のダイアログライン（対角線）が、バウンディングボックスを２つの三角形に分割するものと想定し、これらの三角形を三角形セットに追加する。
５）境界上の点を除くすべての点を三角形セットに挿入する。
【００４７】
ａ）各点について、三角形セットの中の三角形の外接円がその点を含むか、または最後の線分が三角形を通過するか、三角形セットの中のすべての三角形をチェックする。条件が満たされる場合、その三角形を三角形セットから消去し、削除三角形セットに追加する。
【００４８】
ｂ）削除済み三角形セットを使用してポリゴンを拡張し、削除済み三角形セットをただちにクリアする。
【００４９】
ｃ）ポリゴンを使用して三角形セットを生成し、それらを三角形セットに追加する。
【００５０】
図１２Ａ〜図１２Ｈは、ドロネー２Ｄメッシュシーケンスを示している。
【００５１】
＜分割された三角形の削除＞
上のステップでは、分割された三角形にはマークが付される。すべての三角形が横切られた後、本方法は、マークの付いた三角形を削除する。図１４は、削除結果を示している。
【００５２】
＜隠れているファセット＞
２つの三角形セットＡ，Ｂが与えられたとき、ＡがＢの三角形Ｔｂと境界を接している場合、Ｔｂは隠れており、ＢがＡの三角形Ｔａと境界を接している場合、Ｔａは隠れている。
【００５３】
三角形ＴがオブジェクトＯと境界を接しているかをチェックするため、本発明では以下のステップを使用する。
１）三角形Ｔの重心ｃを計算する。
２）線ｌ：ｐ＝ｃ＋ｔ＊Ｎを構築する。この線は重心を始点とし三角形Ｔの法線Ｎに沿って延びる。
３）オブジェクトＯの各三角形Ｔｏについて、線と平面の交点を計算する。三角形Ｔｏの内側である有効な交点ｐｅｔが存在する場合、重心ｃおよびｐｅｔによって決まるｔを計算し、ｔを深さバッファ（ｂｕｆｆｅｒＴ）に追加する。
４）ｂｕｔｔｅｒＴに格納されている負のｔおよび正のｔのサイズをチェックする。２つのサイズが等しい場合、三角形Ｔは境界を接しており隠れている。
【００５４】
サーフェストリムを実行するとき、本システムは、三角形が隠れているかを判定するため以下の手順を呼び出す。
１）関与するサーフェスパッチのＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの各Ｐｏｉｎｔ３ｄＥｘのメンバーｍ＿ＩＤを０に設定する。
２）このパッチの交線のＰｏｉｎｔ３ｄＥｘのｍ＿ＩＤを、この線とトリム輪郭が同じ方向である（例えば両方が左回りである）かに応じて昇順または降順にマークする。
３）各三角形のメンバーｍ＿Ｐｏｉｎｔｓのｍ＿ＩＤに従って、各三角形が境界三角形であるかを判定する。
４）各境界三角形について、その三角形がトリム輪郭の左側であるか右側であるかを判定し、境界三角形ではない隣接三角形を「左」または「右」に設定する。
【００５５】
＜ファセットの再編成＞
本発明は、５種類のブーリアン演算を記載しており、ブーリアン演算それぞれが異なる再編成手順を有する。
【００５６】
結合演算（この演算は論理的にはＯＲである）は、２つのソリッド幾何オブジェクトを結合して新しいオブジェクトを生成し（通常では、外側から見て隠れている区画を破棄し、見えている区画を維持する）、以下の手順を有する。
１）オブジェクトＡの隠れている三角形を削除する。
２）オブジェクトＢの隠れている三角形を削除する。
３）オブジェクトＡの三角形とオブジェクトＢの三角形をマージする。
【００５７】
交差演算（この演算は論理的にはＡＮＤである）（２つの幾何オブジェクトの共通部分（public section）を使用してソリッド幾何オブジェクトを作成し、共有される共通部分の外側のＡおよびＢの区画を破棄する）は、以下の手順を有する。
１）オブジェクトＡの隠れていない三角形を削除する。
２）オブジェクトＢの隠れていない三角形を削除する。
３）オブジェクトＡの三角形とオブジェクトＢの三角形をマージする。
【００５８】
除外演算（２つの幾何オブジェクトの共通部分を除去し、共有されていない区画を保持することによって、ソリッド幾何オブジェクトを構築する）は、以下の手順を有する。
１）オブジェクトＡの隠れている三角形をバッファｂｕｆｆｅｒＡにコピーする。
２）オブジェクトＡから、隠れている三角形を削除する。
３）オブジェクトＢの隠れている三角形をオブジェクトＡにコピーする。
４）オブジェクトＢから、隠れている三角形を削除する。
５）ｂｕｆｆｅｒＡ内の三角形をオブジェクトＢにコピーする。
６）ＡおよびＢのすべての隠れている三角形の法線を反転させる。
７）２つのオブジェクトの三角形をマージする。
【００５９】
差演算（Ｂの内側のＡの区画を除去することによって、幾何オブジェクトＡを別のオブジェクトＢによって切り取る）は、以下の手順を有する。
１）オブジェクトＡの隠れている三角形を削除する。
２）オブジェクトＢの隠れていない三角形を削除する。
３）オブジェクトＢのすべての三角形の法線を反転させる。
４）オブジェクトＡとオブジェクトＢの三角形をマージする。
【００６０】
分割演算（２つのソリッド幾何オブジェクトＡ，Ｂを３つのオブジェクト、すなわち、２つの幾何オブジェクトの共通部分、オブジェクトＡの共有されていない区画、オブジェクトＢの共有されていない区画、に分割する）は、以下の手順を有する。
１）オブジェクトＡの隠れている三角形をバッファｂｕｆｆｅｒＡにコピーする。
２）オブジェクトＢの隠れている三角形をｂｕｆｆｅｒＡにコピーする。
３）オブジェクトＡの隠れている三角形を別のバッファｂｕｆｆｅｒＢにコピーする。
４）オブジェクトＡの隠れている三角形を削除する。
５）オブジェクトＢの隠れている三角形をオブジェクトＡにコピーする。
６）オブジェクトＢの隠れている三角形を削除する。
７）ｂｕｆｆｅｒＡに格納されているオブジェクトＡの隠れている三角形を、オブジェクトＢにコピーする。
８）ＡおよびＢのすべての隠れている三角形の法線を反転させる。
【００６１】
＜レンダリングファセットへのマッピング＞
ブーリアン演算が終了した時点で、本方法は、ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔをレンダリング三角形にマッピングする。
１）ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの各Ｐｏｉｎｔ３ｄＥｘを、ＴｒｉａｎｇｌｅＳｅｔのＰｏｉｎｔ３ｄにマッピングする。
２）ＢｌＯｐＴｒｉａｎｇｌｅＳｅｔの各Ｔｒｉａｎｇｌｅ３ｄＥｘを、ＴｒｉａｎｇｌｅＳｅｔのＴｒｉａｎｇｌｅ３ｄにマッピングする。
【図１】
2019526111.tif 000003
【図２】
2019526111.tif 000004
【図３】
2019526111.tif 000005
【図４】
2019526111.tif 000006
【図５】
2019526111.tif 000007
【図６】
2019526111.tif 000008
【図７】
2019526111.tif 000009
【図８】
2019526111.tif 000010
【図９】
2019526111.tif 000011
【図１０】
2019526111.tif 000012
【図１１】
2019526111.tif 000013
【図１２】
2019526111.tif 000014
【図１３】
2019526111.tif 000015
【図１４】
2019526111.tif 000016
【図１５】
2019526111.tif 000017
【図１６】
2019526111.tif 000018
【図１７】
2019526111.tif 000019
【図１８】
2019526111.tif 000020
【国際調査報告】
2019526111.tif 000021